问题描述

编题面太难了，这次小洞决定放自己一马。

给定一个 n 个点 m 条边的无向图 G, 小栋很好奇 G 上 1 到其他点的最短路的长度。

当然，只要求最短路未免过于简单，小洞希望玩点花的，假设一条路径上的边权依次为 w1, w2, . . . wk,

小洞定义 S(w) = min（wi） − max（wi） + ∑wi 为路径长度，他希望你能帮他求出在这个定义下的最短路。

Input

第一行两个正整数 n, m, 表示图 G 的点数和边数。

接下来 m 行，每行三个整数 u, v, w, 表示 u 和 v 之间有一条边权为 w 的无向边

Output

输出 n − 1 个整数，第 i 行表示，表示 1 到 i + 1 的所有路径中 S(w) = min（wi） − max（wi） + ∑wi 的最小值。

输入样例1:

5 4 

5 3 4 

2 1 1 

3 2 2 

2 4 2

输出样例1:

1 2 2 4

输入样例1:

7 10 

7 5 5 

2 3 3 

4 7 1 

5 3 6 

2 7 6 

6 2 6 

3 7 6 

4 2 1 

3 1 4 

1 7 4

输出样例1:

3 4 2 7 7 3

Notes

对 20% 的数据，n, m ≤ 10

对另外 20% 的数据，图是一棵树。

对另外 20% 的数据，边权均相等。

对 100% 的数据，n, m ≤ 2 × 10^5 , 1 ≤ u, v ≤ n, 0 < w ≤ 10^9 , 数据保证不存在自环。