Bellman_Ford 算法的思路是这样的。令 $d_i$ 为从节点 $1$ 到节点 $i$ 的最短路。扫描所有边 $(x, y, z)$，如果 $d_y > d_x +z$，那么令 $d_y = d_x + z$。如此这样扫描 $m$ 条边，每条边都扫描 $n$ 次，便得到了最短路的值。
而 spfa 则是该算法的一个队列优化。使用队列可以有效避免不需要扫描的节点的扫描，优化了效率，但是写起来更麻烦，极端情况下效率也未必比前者高。并且此题数据范围小，Bellman-Ford完全可以胜任。
当然，我们还可以加一个小优化，就是当循环次数还没有到 $n$ 次时，如果有一次循环中一个节点的最短路值都没有更新，那么就直接跳出循环。（~~虽然这个优化可能没什么用~~）
跑的还挺快，21ms。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long dis[2010];
struct P {
int x, y, z;
} a[2010];
int main() {
scanf("%d%d", &n, &m);
bool flag = 1;
for (register int i = 1; i <= n; ++i) dis[i] = 1e18;
dis[1] = 0;
for (register int i = 1; i <= m; ++i) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
for (register int i = 1; i <= n; ++i) {
flag = 1;
for (register int j = 1; j <= m; ++j)
if (dis[a[j].y] > dis[a[j].x] + a[j].z) flag = 0, dis[a[j].y] = dis[a[j].x] + a[j].z;
if (flag) break;
}
for (register int i = 1; i <= n; ++i) printf("%lld ", dis[i] == 1e18 ? -1 : dis[i]);
}
```