题目描述

某城市有 $N$ 个供水点，编号为 $1$ 到 $N$。有 $M$ 条管道连接这些供水点，第 $i$ 条管道连接供水点 $U_i$ 和 $V_i$，管道长度为 $W_i$。

现在要从供水点 $1$ 出发，将水输送到所有其他供水点。请问从供水点 $1$ 到每个供水点的最短距离是多少？

如果某个供水点无法到达，输出 $-1$。

输入格式

第一行两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行三个整数 $U_i, V_i, W_i$。

输出格式

输出一行 $N$ 个整数，表示从供水点 $1$ 到每个供水点的最短距离。

样例

输入

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

输出

0 2 5 6

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le W_i \le 10^4$。