题目描述

给一个 $n$ 个点 $m$ 条边的有向图（其中某些边权可能为负，但保证没有负环）。

请你计算从 $1$ 号点到其他点的最短路（顶点从 $1$ 到 $n$ 编号）。

输入格式

第一行两个个由空格隔开的整数 $n$ 、$m$；

之后的 $m$ 行，每行三个正整数 $u_i$ 、$v_i$ 、$w_i$ ，表示一条从 $u_i$ 到 $v_i$ 长度为 $w_i$ 的边。

输出格式

输出 $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$，保证从任意顶点都能到达其他所有顶点。