题目描述

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

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

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

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

当精灵进入农场后：

输入格式

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

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

输出格式

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

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

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

样例

输入样例

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

输出样例

3
3
6