道路阻断(Disruption P)

题目描述

Farmer John 自豪于他所经营的交通发达的农场。这个农场由 $N$ 块牧场（$2 \leq N \leq 50,000$）组成，$N-1$ 条双向道路将它们连接起来，每条道路的长度均为 $1$ 单位。Farmer John 注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。

尽管 FJ 的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这会将农场分为两个不相交的牧场集合，奶牛们只能在每个集合内移动而不能在集合间移动。于是 FJ 又建造了 $M$ 条额外的双向道路（$1 \leq M \leq 50,000$），每条道路的长度都是一个至多为 $10^9$ 的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断。

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

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

输入格式

输入的第一行包含 $N$ 和 $M$。接下来的 $N-1$ 行，每行用整数 $p$ 和 $q$ 描述了一条原有的道路，其中 $p \neq q$ 是这条道路连接的两块牧场（在 $1 \ldots N$ 范围内）。剩下的 $M$ 行，每行用三个整数 $p$、$q$ 和 $r$ 描述了一条额外的道路，其中 $r$ 是这条道路的长度。任何两块牧场之间至多只有一条道路。

输出格式

对原有的 $N-1$ 条道路的每一条，按照它们在输入中出现的顺序，输出如果这条道路被阻断的话，能够重新连接农场的最短替代道路的长度。如果不存在合适的替代道路，输出 $-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

数据范围

供题：Brian Dean

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接