Description

Farmer John is proud of his well-connected farm. The farm consists of $N$ pastures ($2 \leq N \leq 50,000$) with $N-1$ bidirectional roads connecting them, each of length $1$ unit. Farmer John notices that from any pasture to any other, one can travel via some sequence of roads.

Although FJ's farm is currently connected, he worries about what would happen if a road were blocked, since this would split the farm into two disjoint sets of pastures, and the cows could move only within each set but not between sets. So FJ builds $M$ additional bidirectional roads ($1 \leq M \leq 50,000$), each with a positive integer length of at most $10^9$. The cows can still use the original roads to travel unless some of them are blocked.

If one of the original roads is blocked, the farm is divided into two disjoint regions. FJ will then choose one of his additional roads that can restore connectivity between these two regions to replace the original one, so that the cows can again travel from any pasture to any other pasture.

For each original road on the farm, help FJ pick the shortest replacement road.

Input Format

The first line contains $N$ and $M$. The next $N-1$ lines each describe an original road with integers $p$ and $q$, where $p \neq q$ are the two pastures it connects (within $1 \ldots N$). The remaining $M$ lines each describe an additional road with three integers $p$, $q$, and $r$, where $r$ is the road's length. There is at most one road between any two pastures.

Output Format

For each of the original $N-1$ roads, in the order they appear in the input, output the length of the shortest replacement road that can reconnect the farm if that road is blocked. If no suitable replacement road exists, output $-1$.

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

7
7
8
5
5

Hint

Author: Brian Dean.

Translated by ChatGPT 5