Disruption#10392
Farmer John prides himself on running a well-connected farm. The farm consists of pastures connected by n - 1 bidirectional pathways, each of unit length. Farmer John notices that, using an appropriate sequence of these pathways, it is possible to travel from any pasture to any other pasture.
Although FJ's farm is connected, he worries about what might happen if one of the pathways gets blocked: this would split his farm into two disjoint sets of pastures, so that the cows could travel within each set but not between the sets. Therefore, FJ builds additional bidirectional pathways, each with a positive integer length not exceeding 10^9. The cows still use only the original pathways, unless one of them becomes blocked.
If one of the original pathways becomes blocked, the farm splits into two disjoint parts, and FJ chooses one of the additional pathways as a replacement that reconnects these two parts, so that the cows can once again travel from any pasture to any other pasture.
For each of the original pathways, help FJ choose the shortest suitable replacement pathway.
The first line contains two integers and m~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 5 \cdot 10^4). Each of the next n - 1 lines describes an original pathway and contains two integers and q~(1 \le p, q \le n, p \ne q) — the pastures connected by this pathway. Each of the next lines describes an additional pathway and contains three integers , , and , where and are the pastures it connects and is its length. Any pair of pastures is connected by at most one pathway.
For each of the n - 1 original pathways, in the order in which they appear in the input, print the length of the shortest suitable replacement pathway that would reconnect the farm if this original pathway were blocked. If no suitable replacement exists, print .
Example 1