说明

给定一个$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 \leqslant 5，m \leqslant 10$
• 对于100%的数据，$1 \leqslant n \leqslant 20000，1 \leqslant m \leqslant 200000，-10000 \leqslant l \leqslant 10000$，保证从任意顶点都能到达其他所有顶点。

来源

牛客网