旅游 【STSR】Round #1

描述

有n-1个人要去旅游，当然他们现在在同一个出发点（点1），他们的目的地各不相同，其中第i个人要去第i个景点(点i+1），当然景点与景点之间有道路连接，通过这些道路需要一定的时间，为了赶时间也为了欣赏沿途的风景，他们约定不走原最短路的最后一条道路，但是要让旅行的时间最短。

(为了保证出题人的良心程度，保证最短路径唯一）

输入格式

行1：两个整数n，m，表示n个景点，m条边。

行2..m+1行：xi，yi，ti，表示有一条从xi到yi的双向道路

输出格式

第1..n-1行：每行一个数表示从出发点到第i个景点（点i+1）的不经过原最短路最后一条道路的最短的旅行时间，无解输出-1

样例输入

4 5

1 2 2

1 3 2

3 4 4

3 2 1

2 4 3

样例输出

3

3

6

数据范围与约定

对于30％的数据，n<=1000,m<=10000

对于100％的数据,n<=10000,m<=200000，保证运算过程中的数字在0到2^31-1范围内。