Description

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

Format

Input

第一行两个整数$n, m$。 接下来的$m$行，每行有三个整数$u, v, l，$表示$u$到$v$有一条长度为$l$的边。
(对于$10\%$的数据，$n = 2，m = 2。$
对于$30\%$的数据，$n \le 5，m \le 10。$
对于$100\%$的数据，$1 \le n \le 20000，1 \le m \le 200000，-10000 \le l \le 10000$
保证从任意顶点都能到达其他所有顶点。)

Output

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

Samples

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

-1 -2