[Usaco2009 Jan]安全路经Travel
时间限制：10s 空间限制：64MB
题目描述
输入格式
* 第一行: 两个空格分开的数, 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 输出解释: 跟题中例子相同
提示
没有写明提示
题目来源
Gold