A group of researchers are studying fish population in a natural system of lakes and rivers. The system contains $n$ lakes connected by $n - 1$ rivers. Each river has integer length (in kilometers) and can be traversed in both directions. It is possible to travel between any pair of lakes by traversing the rivers (that is, the network of lakes and rivers form a tree).
There is an unknown number of indistinguishable fish living in the lakes. On day $1$, fish can be at arbitrary lakes. Fish can travel between lakes by swimming the rivers. Each fish can swim a river $l$ kilometers long in any direction in $l$ days. Further, each fish can stay any number of days in any particular lake it visits. No fish ever appear or disappear from the lake system. Each lake can accomodate any number of fish at any time.
The researchers made several observations. The $j$\-th of these observations is "on day $d_j$ there were at least $f_j$ distinct fish in the lake $p_j$". Help the researchers in determining the smallest possible total number of fish living in the lake system that doesn't contradict the observations.
## Input
The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of lakes in the system.
The next $n - 1$ lines describe the rivers. The $i$\-th of these lines contains three integers $u_i$, $v_i$, $l_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq l_i \leq 10^3$) — $1$\-based indices of lakes connected by the $i$\-th river, and the length of this river.
The next line contains a single integer $k$ ($1 \leq k \leq 10^5$) — the number of observations.
The next $k$ lines describe the observations. The $j$\-th of these lines contains three integers $d_j$, $f_j$, $p_j$ ($1 \leq d_j \leq 10^8$, $1 \leq f_j \leq 10^4$, $1 \leq p_j \leq n$) — the day, the number of fish, and the lake index of the $j$\-th observation. No two observations happen on the same day at the same lake simultaneously.
## Output
Print one integer — the smallest total number of fish not contradicting the observations.
[samples]
## Note
In the first example, there could be one fish swimming through lakes $2$, $1$, and $4$, and the second fish swimming through lakes $3$, $1$, and $2$.
In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming $2 \to 1 \to 4$ and $3 \to 1 \to 5$ can.
In the third example one fish can move from lake $1$ to lake $5$, others staying in their lakes during all time: two fish in lake $4$, six fish in lake $5$, one fish in lake $3$. The system of lakes is shown on the picture.
<center></center>
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of lakes.
Let $ T = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $ (lakes) and $ E $ the set of $ n-1 $ edges (rivers).
Each edge $ e = (u, v, l) \in E $ has a positive integer weight $ l \in \mathbb{Z}^+ $ representing the river length.
Let $ d(u, v) $ denote the shortest path distance (sum of edge weights) between lakes $ u $ and $ v $ in $ T $.
Let $ k \in \mathbb{Z}^+ $ be the number of observations.
Each observation $ j \in \{1, \dots, k\} $ is a triple $ (d_j, f_j, p_j) $, where:
- $ d_j \in \mathbb{Z}^+ $ is the day of observation,
- $ f_j \in \mathbb{Z}^+ $ is the minimum number of distinct fish observed in lake $ p_j $ on day $ d_j $,
- $ p_j \in V $ is the lake index.
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le l_i \le 10^3 $ for all rivers
3. $ 1 \le k \le 10^5 $
4. $ 1 \le d_j \le 10^8 $, $ 1 \le f_j \le 10^4 $, $ 1 \le p_j \le n $ for all observations
5. All $ (d_j, p_j) $ pairs are distinct.
**Objective**
Find the minimum total number of fish $ F \in \mathbb{Z}^+ $ such that there exists a set $ \mathcal{F} $ of $ F $ fish paths satisfying:
- Each fish follows a continuous walk (possibly with pauses) in the tree $ T $, moving along edges at speed 1 km/day.
- For each observation $ j $, at least $ f_j $ fish are present in lake $ p_j $ at time $ d_j $.
- Fish never enter or leave the system.
Equivalently, define for each fish a path $ \pi: \mathbb{R}_{\ge 0} \to V $, such that $ \pi(t) $ is the lake occupied by the fish at time $ t $, with $ d(\pi(t), \pi(t')) \le |t - t'| $ for all $ t, t' \ge 0 $.
Let $ \mathcal{O} = \{ (d_j, p_j, f_j) \}_{j=1}^k $.
Minimize $ |\mathcal{F}| $ such that for each $ j $:
$$
\left| \left\{ f \in \mathcal{F} \mid \pi_f(d_j) = p_j \right\} \right| \ge f_j
$$
This is equivalent to covering the observation constraints with minimum number of fish paths, where a fish can satisfy multiple observations $ (d_j, p_j) $ if $ d(p_i, p_j) \le |d_i - d_j| $.
**Reformulation as Minimum Path Cover under Temporal Distance Constraints**
Let $ G = (V_{\text{obs}}, E_{\text{feas}}) $ be a directed graph where:
- Each node $ v_j \in V_{\text{obs}} $ corresponds to observation $ j $,
- There is a directed edge $ v_i \to v_j $ if a single fish can visit $ p_i $ at time $ d_i $ and $ p_j $ at time $ d_j $, i.e.,
$$
d(p_i, p_j) \le d_j - d_i \quad \text{and} \quad d_j > d_i
$$
Let $ w_j = f_j $ be the demand at node $ v_j $.
The problem reduces to finding the minimum number of paths in $ G $ (each path representing one fish’s itinerary) such that each node $ v_j $ is covered by at least $ w_j $ paths.
This is the **Minimum Weighted Path Cover with Demands** problem on a DAG.
**Objective (Final Formal Statement)**
Let $ G = (V_{\text{obs}}, E_{\text{feas}}) $ be the DAG defined above, with node weights $ w_j = f_j $.
Find the minimum number of paths in $ G $ such that each node $ j $ is covered by at least $ w_j $ paths.
This minimum is equal to:
$$
\max_{S \subseteq V_{\text{obs}}} \left( \sum_{j \in S} f_j - \sum_{\substack{i \to j \in E_{\text{feas}} \\ i \in S, j \notin S}} \min(f_i, f_j) \right)
$$
but more efficiently computed via **minimum flow** in a transformed network:
**Transformed Network for Minimum Flow**
Construct a flow network:
- Source $ s $, sink $ t $.
- For each observation $ j $, create a node $ u_j $.
- Add edge $ s \to u_j $ with capacity $ f_j $.
- Add edge $ u_j \to t $ with capacity $ f_j $.
- For each feasible edge $ i \to j $ in $ G $, add edge $ u_i \to u_j $ with infinite capacity.
- Compute minimum $ s $-$ t $ flow such that all $ s \to u_j $ edges are saturated.
Then, the **minimum number of fish** is equal to the value of this minimum flow.
Alternatively, by duality, it is the **maximum total demand minus maximum possible "sharing"** — but the cleanest formal statement is:
**Objective**
Compute the minimum number of fish $ F $ such that there exists a set of $ F $ walks in the tree $ T $, each walk being a time-respecting path (speed ≤ 1 km/day), satisfying all observation constraints $ \text{fish count at } (d_j, p_j) \ge f_j $.
This equals the **minimum flow** in the transformed network above.
But for direct mathematical output:
---
**Objective**
Let $ G = (V_{\text{obs}}, E_{\text{feas}}) $ be a directed graph with $ V_{\text{obs}} = \{1, \dots, k\} $, and
$$
(i, j) \in E_{\text{feas}} \iff d_j > d_i \text{ and } d(p_i, p_j) \le d_j - d_i
$$
Let $ w_j = f_j $.
Then the minimal number of fish is:
$$
\min \left\{ F \in \mathbb{Z}^+ \,\middle|\, \exists \text{ a collection of } F \text{ paths in } G \text{ such that } \sum_{P \ni j} 1 \ge w_j \ \forall j \in \{1,\dots,k\} \right\}
$$
This is the **minimum weighted path cover** of the DAG $ G $ with node demands $ w_j $.
Equivalently, via flow:
Construct network $ \mathcal{N} $:
- Nodes: $ s, t $, and $ u_j $ for each observation $ j $.
- Edges:
- $ s \to u_j $, capacity $ w_j $
- $ u_j \to t $, capacity $ w_j $
- $ u_i \to u_j $, capacity $ \infty $ for each $ (i,j) \in E_{\text{feas}} $
Then:
$$
\boxed{F = \text{min-flow}(s, t) \text{ in } \mathcal{N}}
$$