Minimum Replacement Road

Farmer John has a farm consisting of N pastures (with 2 \le N \le 50{,}000) connected by N-1 bidirectional roads (each of unit length) which form a tree. He has also built M extra bidirectional roads (with 1 \le M \le 50{,}000), where each extra road has a positive integer length at most \(10^9\).

For any original road (edge) in the tree, if it becomes blocked the tree splits into two connected components. Farmer John wants to select one of the extra roads that reconnects these two components; that is, an extra road whose endpoints lie in different components. Among all such extra roads, he wishes to choose the one with the minimum length. If there is no extra road that reconnects the two parts, output \(-1\) for that blocked road.

Formally, let the tree have vertices \(\{1,2,\dots,N\}\) and let the extra roads be given as triples \((u,v,w)\). For each tree edge \(e\) (which when removed splits the vertices into two sets \(S\) and \(\overline{S}\)), find \[ ans_e = \min\{w\mid \text{the extra road }(u,v,w)\text{ satisfies }(u\in S\text{ and }v\in \overline{S}) \text{ or } (u\in \overline{S}\text{ and }v\in S)\}\] with \(ans_e = -1\) if no such extra road exists.

Note: The input guarantees that the tree is connected and that any two pastures are connected by a sequence of roads. However, after an original road is blocked, only extra roads (if chosen) will be used to reconnect the two separated parts.

inputFormat

The first line contains two integers \(N\) and \(M\). The next \(N-1\) lines each contain two integers \(u\) and \(v\) indicating an original road between pastures \(u\) and \(v\). The following \(M\) lines each contain three integers \(u\), \(v\), and \(w\) representing an extra road connecting pastures \(u\) and \(v\) with length \(w\). The pastures are numbered from 1 to \(N\).

outputFormat

Output \(N-1\) lines. The \(i\)-th line should contain the minimum replacement road length for the \(i\)-th original road (in the same order as the input). If there is no extra road that reconnects the two components when that road is blocked, output \(-1\) for that road.

sample

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

10
5
5