Your town has \(N\) junctions numbered \(1\) to \(N\). These junctions are connected by exactly \(N-1\) bidirectional roads in such a way that there is a unique simple path between each pair of junctions.

\(M\) oil tankers are transported through the town. Each of these tankers had oil leaking from them. It is known that the amount of oil that is leaking increases by one per road as the tanker moves ahead on its path. In other words, if \(K\) liters of oil spills on the road between the \(i^{th}\) and \((i+1)^{th}\) junction on its path, then up to \(K+1\) litres of oil can spill on the road between the \((i+1)^{th}\) and \((i+2)^{th}\) junction on its path.

For each \(j\) such that \(1 \le j \le M\), you know \(S_j\), \(D_j\), and \(L_j\) that denote the source, destination, and the amount of oil in the \(j^{th}\) tanker. Also, you know that exactly one liter of oil is spilled on the first road on the path of each of the tankers.

It is obvious that the amount of oil spilled from an oil tanker can't exceed the amount of oil it was carrying.

You are currently at junction \(1\). You select a junction \(X\) and travel from junction \(1\) to junction \(X \). Now, you collect all the spilled oil on the roads that you travel along the way. If you choose \(X\) optimally, then what is the maximum amount of oil that you can collect?

Input format

• The first line of input contains the integer \(N\text{ }(2 \le N \le 2\cdot10^5)\).
• The next \(N-1\) lines contain two space-separated integers \(u,v\text{ }(1 \le u,v \le N)\) denoting a bidirectional road between junction \(u\) and junction \(v\).
• The next line contains the integer \(M\text{ }(1 \le M \le 2\cdot 10^5)\).
• The next \(M\) lines contain three space-separated integers \(S_j\), \(D_j\), and \(L_j\) \((1\le S_j,\ D_j \le N,\ 1 \le L_j \le 10^9)\) denoting the source, destination, and the amount of oil in the \(j^{th}\) oil tanker.

Output format

In the only line of the output, print a single integer denoting the answer to the problem.