描述

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