题目描述

精灵最近在农场上泛滥，它们经常会阻止牛们从农庄${(}$牛棚${1)}$走到别的牛棚${(}$牛${i}$的目的地是牛棚${i)，}$每一个精灵只认识牛${i}$并 且知道牛${i}$一般走到牛棚${i}$的最短路经，所以它们在牛到牛棚之前的最后一条牛路上等牛${i}$。

当然，牛不愿意遇到精灵，所以准备找一条稍微不同的路经从牛棚${1}$走到牛棚${i}$。所以，请你为每一头牛${i}$找出避免精灵的最短路经的长度。

和以往一样，农场上的${M(2<M<200000)}$条双向牛路编号为${1}$到${M}$并且能让所有牛到达它们的目的地，${N(3 ≤}$${N< 100000)}$个牛棚，牛路${i}$连接牛棚${a_i}$和${b_i}$${(1≤}$${a_i}$${b_i}$${≤}$ ${N)}$并且需要时间${t_i}$${(1<t_i}$${<1000)}$通过，没有两条牛路 连接同样的牛棚，所有牛路满足${a_i≠}$ ${b_i}$在所有数据中，牛${i}$使用的牛棚${1}$到牛棚${i}$的最短路经是唯一的。

以下是一个牛棚，牛路和时间的例子:

当精灵进入农场后：

输入格式

第一行: 两个空格分开的数, ${N}$和${M}$

第${2..M+1}$行: 三个空格分开的数${a_i, b_i,}$和${t_i}$

输出格式

第${1..N-1}$行:

第${i}$行包含一个数:从牛棚${_1}$到牛棚${_i+1}$并且避免从牛棚${1}$到牛棚${i+1}$最短路经上最后一条牛路的最少的时间.

如果这样的路经不存在,输出${-1.}$

样例

输入样例

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

输出样例

3
3
6