题目描述

有 $n$ 个城市和 $m$ 条航班连接它们。你的任务是确定从 Syrjälä（城市 $1$）到每个城市的最短路径长度。每个航班都是单向的，并有一个长度。可以假设从城市 $1$ 可以到达所有其他城市。

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示城市的数量和航班连接的数量。城市编号为 $1,2,\dots,n$，城市 $1$ 是 Syrjälä。

接下来的 $m$ 行，每行包含三个整数 $a$, $b$, $c$：表示一条从城市 $a$ 到城市 $b$ 的单向航班，航班的长度是 $c$。

输出格式

输出 $n$ 个整数，用空格分隔，表示从城市 $1$ 到城市 $1,2,\dots,n$ 的最短路径长度。

样例

3 4
1 2 6
1 3 2
3 2 3
1 3 4

0 5 2

样例解释
从城市 $1$ 到城市 $1$ 的距离为 $0$。到城市 $2$ 的最短路径为 $1\to3\to2$，长度 $2+3=5$。到城市 $3$ 的最短距离为 $1\to3$，长度为 $2$。

数据范围

• $1 \le n \le 10^5$
• $1 \le m \le 2 \times 10^5$
• $1 \le a,b \le n$
• $1 \le c \le 10^9$