由于频繁有台风登陆，A 国如今受到狂风暴雨的洗礼。在这种恶劣的环境中，保证交通畅通是 A 国王首要关心的事情。A 国当前的交通情况是由 N-1 条双向道路将 N 个城市联通起来，其中每条道路的长度都是 1。需要注意，任意两个城市都是可以互相到达的。

A 国王为了应对某条道路阻断后带来的不好的结果，他决定启用备用道路，现在一共有 M 条备用的双向道路，每一条的长度均为一个至多为 10^9 的正整数。人们仍然可以使用未被阻断的原有道路进行移动。

如果某条原有的道路被阻断了，整个国家就会被分为两块不相交的区域，那么 A 国王就会从额外修建的道路中选择一条能够使这两块区域连通的，取代被阻断的那条，从而使得整个国家重新联通起来。

对于 A 国的每一条原有的道路，帮助 A 国王选出最短的替代用的道路。

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

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

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