Problem
给定一个有向图，它可以有多个边和环。每条边都有一个表示为整数（可能为负）的权重。保证没有负权重循环。
您需要计算从顶点编号 1 到所有其他顶点的最短路径的长度。
输入
程序首先接收到数字N(1 <= N <= 100) –图顶点的数量和数量 M (0 <= M <= 10000) –肋骨数。以下行包含描述边的 M 个数字三元组：边的起点、边的终点和权重（权重 – 是从 -100 到 100 的整数）。
输出
程序应该输出N个数字–从顶点编号 1 到图中所有顶点的距离。如果没有到相应顶点的路径，则打印数字 30000 而不是路径长度。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |