一个国家有 $n$ 个城市，它们之间由 $n - 1$ 条道路相连。第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，通过该道路需要花费 $w_i$ 单位的时间。任意两个城市之间都可以通过这些道路相互到达，从而形成了一棵树。由于该国的科技非常发达，每个城市都设有一个传送门。这些传送门之间有 $m$ 条传送通道。第 $i$ 条通道连接城市 $p_i$ 和 $q_i$ 的传送门。如果一个人在城市 $u$，且存在一条直接连接这两个城市传送门的传送通道，那么他可以不花任何时间旅行到城市 $v$。由于传送非常昂贵，人们在旅途中最多只能使用 $k$ 次传送门。

小 N 是该国的交通部长。他想要评估这个交通网络的效率。具体来说，他想针对每个 $k = 0, 1, \dots, n$，计算 $\sum_{u=1}^{n} d(u, k)$ 的值，其中 $d(u, k)$ 表示在最多使用 $k$ 次传送门的情况下，从城市 $u$ 旅行到城市 $1$ 的最小时间花费。由于计算对他来说过于复杂，他希望你设计一个程序来帮他计算。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 5000$，$0 \le m \le 10000$），分别表示城市数量和传送通道数量。

接下来的 $n - 1$ 行，每行包含三个整数；第 $i$ 行包含三个整数 $u_i$、$v_i$ 和 $w_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$），表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，通过该道路需要花费 $w_i$ 单位的时间。

接下来的 $m$ 行，每行包含两个整数；第 $i$ 行包含两个整数 $p_i$ 和 $q_i$（$1 \le p_i, q_i \le n$），表示第 $i$ 条传送通道连接城市 $p_i$ 和 $q_i$ 的传送门。

输出格式

输出应包含 $n + 1$ 行；第 $i$ 行应包含一个整数，表示 $k = i - 1$ 时的结果。

样例

样例输入 1

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

样例输出 1

30
8
4
0
0
0