题目描述

题目译自 USACO 2018 US Open Contest, Platinum Problem 3. Disruption

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

input

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

output

7
7
8
5
5

数据范围与提示

对于全部数据，$2\le N\le 5\times 10^4,1\le M\le 5\times 10^4,1\le p,q\le N,p \neq q$。

Problem credits: Brian Dean