#1576. [Usaco2009 Jan]安全路经Travel

题目描述

.jpg)

输入格式

• 第一行: 两个空格分开的数, 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  

  

输出解释:  

  

跟题中例子相同  

数据范围与提示