【题目描述】

有 $n$ 个城市和 $m$ 条带长度的双向道路。求城市 $1$ 到所有城市的最短路长度，无法到达输出 -1。

【输入格式】

$n$   $m$

$u_1$   $v_1$   $w_1$

$\vdots$

【输出格式】

输出一行 $n$ 个最短距离。

【样例】

4 4
1 2 5
2 3 2
1 3 10
3 4 1

0 5 7 8

【数据范围】

• $1\le n,m\le100000$
• $0\le w_i\le10^9$