时间限制：1秒　　内存限制：256M

---

【题目描述】

　　灵最近在农场上泛滥，他们经常会阻止牛们从农庄（牛棚 1）走到别的牛棚（牛 \(i\) 的目的地是牛棚 \(i\)）。每一个精灵只认识牛 \(i\) 并且知道牛 \(i\) 一般走到牛棚 \(i\) 的最短路径。所以他们在牛 \(i\) 到牛棚 \(i\) 之间的最后一条牛路上等牛 \(i\)。当然，牛不愿意遇到精灵，所以准备找一条稍微不同的路径从牛棚 1 走到牛棚 \(i\)。请你为每一头牛 \(i\) 找出避免精灵的最短路径长度。

　　和往常一样，农场上有 \(n\) 个牛棚（编号为 \(1..n\)）， \(m\) 条双向牛路（编号为 \(1..m\)）把牛棚连接起来，能让所有牛到达它们的目的地。牛路 \(i\) 连接牛棚 \(a_i\) 和 \(b_i\) 并且需要时间 \(t_i（1≤t_i≤1000）\) 通过。没有两条牛路连接同样的牛棚，所有牛路满足 \(a_i!=b_i\)。所有数据中，牛 \(i\) 使用的牛棚 1 到牛棚 \(i\) 的最短路径是唯一的。

【输入格式】

　　第一行包含两个空格分开的整数：\(n,m\)。之后的 \(m\) 行，每行包含三个空格分开的数 \(a_i,b_i,t_i\)，表示一条牛路连接的 \(a_i,b_i\) 两个牛棚，通过这条牛路的时间为 \(t_i\)。

【输出格式】

　　第 1 到 \(n-1\) 行：第 \(i\) 行包含一个数，从牛棚 1 到牛棚 \(i+1\) 并且避免从牛棚 1 到牛棚 \(i+1\) 最短路径上最后一条牛路的最少的时间。如果这样的路径不存在，输出 -1。

【输入输出样例】

　Input

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

　Output

3
3
6

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(2≤m≤200000\)。

【来源】

　　Mr.he