1576 - [Usaco2009 Jan]安全路经Travel

输入

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

输出解释:

跟题中例子相同
时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题