Disruption

Farmer John's farm has $N$ pastures ($2 \leq N \leq 50{,}000$), joined by $N-1$ two-way paths of unit length. Using these paths, the cows can travel from any pasture to any other pasture.

The farm is connected, but Farmer John worries about a blocked path. Blocking one path splits the farm into two groups of pastures, and the cows can then travel inside a group but not between the two groups. So Farmer John builds $M$ extra two-way paths ($1 \leq M \leq 50{,}000$), each with a positive integer length of at most $10^9$. The cows still use only the original paths, unless one of the original paths becomes blocked.

When an original path becomes blocked, the farm splits into two pieces, and Farmer John picks a single extra path that reconnects the two pieces, so the cows can travel from any pasture to any other pasture again.

For each original path, find the shortest extra path that can replace it.

The first line contains $N$ and $M$. Each of the next $N-1$ lines describes an original path with two integers $p$ and $q$, the pastures it connects, where $p \neq q$ and both lie in the range $1 \ldots N$. Each of the remaining $M$ lines describes an extra path with three integers $p$, $q$, and $r$, where $r$ is the length of the path between pastures $p$ and $q$. At most one path runs between any pair of pastures.

Print $N-1$ lines. On the $i$-th line, print the length of the shortest extra path that reconnects the farm when the $i$-th original path of the input becomes blocked. If no extra path can replace it, print -1.