2930. [USACO Open18 Platinum]Disruption

【题目描述】

Farmer John 自豪于他所经营的交通发达的的农场。这个农场是由 $N$ 块牧场（$2≤N≤50,000$）组成的，$N−1$ 条双向道路将它们连接起来，每一条道路的都为一单位长度。Farmer John 注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。尽管 FJ 的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是 FJ 又建造了 $M$ 条额外的双向道路（$1≤M≤ 50,000$），每一条的长度都是一个至多为 $10^9$ 的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断了。

如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那么 FJ 就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条，从而奶牛们又可以从任何一块牧场去往另一块牧场。

对于农场上每一条原有的道路，帮助FJ选出最短的替代用的道路。

【输入格式】

输入的第一行包含 $N$ 和 $M$。

接下来的 $N−1$ 行，每行用整数 $p$ 和 $q$ 描述了一条原有的道路，其中 $p≠q$ 是这条道路连接的两块牧场（在 $1…N$ 范围内）。

剩下的 $M$ 行，每行用三个整数 $p$、$q$和$r$ 描述了一条额外的道路，其中 $r$ 是这条道路的长度。

任何两块牧场之间至多只有一条道路。

【输出格式】

对原有的 $N−1$ 条道路的每一条，按照它们在输入中出现的顺序，输出如果这条道路被阻断的话，能够重新连接农场的最短的替代用道路的长度。

如果不存在合适的替代用的道路，输出 -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