Pisces

Description:

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.

Sample Input:

4
1 2 1
1 3 1
1 4 1
5
1 1 2
1 1 3
2 2 1
3 1 4
3 1 2

Sample Output:

2

Sample Input:

5
1 2 1
1 3 1
1 4 1
1 5 1
4
1 1 2
2 1 3
3 1 4
4 1 5

Sample Output:

2

Sample Input:

5
2 5 1
5 1 1
2 4 1
5 3 3
6
5 2 4
2 1 1
2 1 3
2 2 4
4 7 5
4 1 2

Sample Output:

10

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.