牧场联通性维护

题目描述

Y 同学经营着一个拥有 $N$ 个牧场的农场，这些牧场通过 $N-1$ 条双向道路相连，形成一个树状结构。每条原始道路的长度均为 $1$ 单位。Y 同学保证，最初从任何一个牧场出发，都可以通过这些道路到达其他任意牧场。

尽管农场目前是连通的，但 Y 同学担心某条原始道路可能会因为维护而失效。如果某条原始道路被阻断，农场将会分裂成两个不相交的连通块。为了应对这种情况，Y 同学预先规划了 $M$ 条额外的双向备份道路。每条备份道路连接两个牧场 $u$ 和 $v$，其权值为 $w$。

Y 同学希望对于每一条原始道路，计算出：如果该道路被阻断，为了使农场重新恢复连通，所能选择的权值最小的备份道路的权值是多少。

输入格式

第一行包含两个正整数 $N$ 和 $M$。

接下来的 $N-1$ 行，每行包含两个正整数 $u$ 和 $v$（$1 \le u, v \le N$，$u \neq v$），表示农场中一条原始道路连接的两个牧场编号。原始道路按照输入顺序从 $1$ 到 $N-1$ 编号。

接下来的 $M$ 行，每行包含三个正整数 $u, v$ 和 $w$（$1 \le u, v \le N$，$1 \le w \le 10^9$），表示一条连接 $u$ 和 $v$ 的备份道路，其权值为 $w$。

输出格式

输出 $N-1$ 行，每行包含一个整数。第 $i$ 行的整数表示第 $i$ 条原始道路被阻断时，能够重新连接农场的最短备份道路的权值。如果不存在任何备份道路能够修复连通性，请输出 $-1$。

样例

样例输入 #1

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

样例输出 #1

7
7
8
5
5

数据范围与约定

对于 100% 的数据，保证 $2 \le N \le 5 \times 10^4$，$1 \le M \le 5 \times 10^4$，$1 \le w \le 10^9$。

特殊性质 A：保证给定的原始道路构成的树是一条链。 特殊性质 B：保证所有备份道路的权值 $w$ 均相等。