说明

给定一个$n$个顶点，$m$条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从$1$号点到其他点的最短路（顶点从$1$到$n$编号）。

输入格式

输入描述:

第一行两个整数$n, m$。

接下来的$m$行，每行有三个整数$u, v, l$，表示$u$到$v$有一条长度为$l$的边。

输出格式

输出描述:
共$n-1$行，第$i$行表示$1$号点到$i+1$号点的最短路。

样例

3 3
1 2 -1
2 3 -1
3 1 2 

-1
-2

提示

对于10%的数据，n = 2，m = 2。

对于30%的数据，n ≤ 5，m ≤ 10。

对于100%的数据，1 ≤ n ≤ 20000，1 ≤ m ≤ 200000，-10000 ≤ l ≤ 10000，保证从任意顶点都能到达其他所有顶点。