Disruption

题目描述

农夫约翰以经营一个四通八达的农场而自豪。该农场由 $N$ 个牧场组成（$2 \leq N \leq 50,000$），其中一些牧场对之间通过 $N-1$ 条双向通路连接，每条通路长度为 1。农夫约翰注意到，通过适当选择这些通路的序列，可以从任意一个牧场到达任意另一个牧场。 尽管 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。

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

提示

题目提供者：Brian Dean

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum