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

数据范围:
110011000
1,5001000

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