说明

某个地区有 $N$ 座火车站和 $M$ 条单向铁路，每条铁路都连接着两座火车站。 每座火车站都有一个自己的编号，分别为 $1\sim N$。 其中，中央车站的编号为 $1$。 求从中央车站出发到每座火车站的最短距离是多少。

输入格式

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

第二行开始的 $M$ 行，每行包含三个正整数 $u, v, w$ ，表示从编号 $u$ 的站点出发 到编号 $v$ 的站点，存在一条长度为 $w$ 的铁路。

输出格式

一行，共 $N$ 个数字，分别表示从中央车站出发到编号 $1\sim N$ 的车站的最短距离，单个空格隔开，如无法到达则输出 $-1$。

样例

3 3 
1 2 1 
1 3 5 
2 3 2

0 1 3

提示

数据范围： $1\le N \le 3 \times 10^5, 1\le M \le 10^6, 1 \le u,v \le N, 0 \le w \le 10^9$