【模板】Bellman-Ford
说明
传说在某个地区有 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个城市，编号分别为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>∼</mo><mi>�</mi></mrow></semantics></math>1∼n，城市之间共有 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 条交通路线。
而 仔仔 是一家公司的打工仔，公司的总公司设在 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow></semantics></math>1 市，公司的业务范围覆盖了全部的 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个城市。
因为公司的安排，苦逼的 仔仔 经常要去各个城市出差，而且差旅费还不报销！
为了能精打细算地省钱，仔仔 统计了各个城市之前交通费分别是多少，大多都是要花钱的路线，但是由于 仔仔 有一些内部渠道，在走某些路线的时候甚至能赚一些钱。
于是 仔仔 想知道从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow></semantics></math>1 市出发前往各个城市的最少花费是多少。但是可选的交通路线太多了，价格也各不相同，他希望编程大神的你能帮忙计算一下。
输入格式
第一行两个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mtext>、</mtext><mi>�</mi></mrow></semantics></math>n、m，分别表示城市数量和交通路线的数量接下来 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 行，每行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>3</mn></mrow></semantics></math>3 个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mtext>、</mtext><mi>�</mi><mtext>、</mtext><mi>�</mi></mrow></semantics></math>u、v、w，表示该路线从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>u 市出发到 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>v 市，需要花费 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>w 元。
注意： 当 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>w 为负数的时候表示走这条路线反而可以赚钱。
输出格式
共一行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数，分别表示从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow></semantics></math>1 市出发到 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>i 市的最少的花费，如果不能到达，输出 no样例
7 7
4 6 3
5 6 4
5 4 -2
3 4 2
3 2 5
1 5 8
1 3 3
0 8 3 5 8 8 no
提示
数据范围：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>�</mi><mo>≤</mo><mn>100</mn><mtext>，</mtext><mn>1</mn><mo>≤</mo><mi>�</mi><mo>≤</mo><mn>1000</mn></mrow></semantics></math>1≤n≤100，1≤m≤1000
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>≤</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo>≤</mo><mi>�</mi><mtext>，</mtext><mo>−</mo><mn>500</mn><mo>≤</mo><mi>�</mi><mo>≤</mo><mn>1000</mn></mrow></semantics></math>1≤u,v≤n，−500≤w≤1000
数据保证不存在花费为负数的环路。