#2871. 「USACO 2018 US Open Platinum」Disruption

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

Farmer John 自豪于他所经营的交通发达的的农场。这个农场是由 NNN 块牧场组成的,N−1N−1N1 条双向道路将它们连接起来,每一条道路的长度都为 111 单位长度。Farmer John 注意到,任意两个牧场都是互相可达的。

尽管 FJ 的农场现在是连通的,但他担心如果有一条道路被阻断会发生什么。事实上,这会将他的农场分为两个不相交的牧场集合,奶牛们只能在一个集合内移动但不能在集合间移动。于是 FJ 又建造了 MMM 条额外的双向道路,每一条的长度均为一个至多为 10910^9109 的正整数。奶牛们仍然可以使用未被阻断的原有道路进行移动。

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

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

输入格式

输入的第一行包含 NNNMMM

接下来的 N−1N−1N1 行,每行用整数 pppqqq 描述了一条原有的道路,其中 p,qp,qp,q 是这条道路连接的两块牧场。

剩下的 MMM 行,每行用三个整数 p,qp,qp,qrrr 描述了一条额外的道路,其中 rrr 是这条道路的长度。任何两块牧场之间至多只有一条额外的道路。

输出格式

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

样例

样例输入

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

数据范围与提示

对于全部数据,2≤N≤5×104,1≤M≤5×104,1≤p,q≤N,p≠q2\le N\le 5\times 10^4,1\le M\le 5\times 10^4,1\le p,q\le N,p =\not q2N5×104,1M5×104,1p,qN,p≠q

Problem credits: Brian Dean