6499: 【模板】Bellman-Ford

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：20 Solved：12

Description

传说在某个地区有 � 个城市，编号分别为 1∼�，城市之间共有 � 条交通路线。

而 仔仔 是一家公司的打工仔，公司的总公司设在 1 市，公司的业务范围覆盖了全部的 � 个城市。
因为公司的安排，苦逼的 仔仔 经常要去各个城市出差，而且差旅费还不报销！

为了能精打细算地省钱，仔仔 统计了各个城市之前交通费分别是多少，大多都是要花钱的路线，但是由于 仔仔 有一些内部渠道，在走某些路线的时候甚至能赚一些钱。

于是 仔仔 想知道从 1 市出发前往各个城市的最少花费是多少。但是可选的交通路线太多了，价格也各不相同，他希望编程大神的你能帮忙计算一下。

Input

第一行两个整数 �、�，分别表示城市数量和交通路线的数量
接下来 � 行，每行 3 个整数 �、�、�，表示该路线从 � 市出发到 � 市，需要花费 � 元。
注意： 当 � 为负数的时候表示走这条路线反而可以赚钱。

Output

共一行 � 个整数，分别表示从 1 市出发到 � 市的最少的花费，如果不能到达，输出 no

Sample Input Copy 

7 7
4 6 3
5 6 4
5 4 -2
3 4 2
3 2 5
1 5 8
1 3 3

Sample Output Copy 

0 8 3 5 8 8 no

HINT

数据范围：
1≤�≤100，1≤�≤1000
1≤�,�≤�，−500≤�≤1000

数据保证不存在花费为负数的环路。

Source/Category

SubmitSubmit RecordStatisticsShowOff!