| 问题描述 |
|---|
给你一个包含 n 个点，m 条边的有向图，输出各个点之间的最短路径。 |
| 输入描述 |
第一行包含两个正整数 n 和 m。(1 <= n <= 100，1 <= m <= 2500) 然后是 m 行，每行三个数字 x、y、z，代表顶点 x 到顶点 y 有一条长度为 z 的边。（1 <= x、y <= n，1 <= z <= 100） |
| 输出描述 |
n 行 n 列，第 i 行第 j 列表示顶点 i 到顶点 j 的最短路径，如果无最短路径，输出 -1。 每两个数字中间用空格隔开，每行最后一个数字后面没有空格，每行输出结束之后都要换行。 |
| 样例输入复制样例 |
3 3 1 2 1 2 3 2 3 1 3 |
| 样例输出 |
0 1 3 5 0 2 3 4 0 |
| 提示说明 |
可能会有自环和重边，遇到重边时，取最小值。 |
| 相关 |