题目描述

给定一个有 n 个顶点（顶点编号为 1~n）的有向图（允许存在重边和自环），图中共有 m 条带权边，边的权值为非负整数（范围 0~1000）。

请你使用弗洛伊德算法，计算出任意两个顶点之间的最短路径长度。若两个顶点之间不存在可达路径，输出 -1。

输入格式

1. 第一行输入两个整数 n 和 m（1 ≤ n ≤ 100，1 ≤ m ≤ 10000），分别表示顶点数和边数；
2. 接下来 m 行，每行输入三个整数 u、v、w，表示存在一条从顶点 u 指向顶点 v 的有向边，边的权值为 w；
3. 顶点编号保证为 1~n 范围内的整数。

输出格式

输出 n 行，每行输出 n 个整数，第 i 行第 j 列的整数表示从顶点 i 到顶点 j 的最短路径长度。若 i 无法到达 j，输出 -1。

输入样例

4 5
1 2 3
1 3 6
2 3 2
2 4 5
3 4 1

输出样例

0 3 5 6
-1 0 2 3
-1 -1 0 1
-1 -1 -1 0

样例解释

• 顶点 1 到顶点 4 的最短路径为 1→2→3→4，总权值 3+2+1=6；
• 顶点 2 到顶点 4 的最短路径为 2→3→4，总权值 2+1=3；
• 顶点 3 无法到达顶点 1、2，故对应位置输出 -1。