题目描述

给出一个包含 (n) 个点的有向图，每条边的权值均为正数。请你求出任意两点之间的最短路径长度，并输出对应的最短距离矩阵。若两点之间不可达，则输出 INF。

格式

输入

第一行两个整数 (n, m)（(1 \le n \le 100)），表示图的点数和边数。 接下来 (m) 行，每行三个整数 (u, v, w)，表示一条从 (u) 到 (v) 的有向边，边权为 (w)（(1 \le w \le 100)）。 点的编号为 (1 \sim n)。

注意：

• 图中可能存在重边，请保留权值最小的一条。
• 任意两点之间不一定连通。

输出

输出一个 (n \times n) 的矩阵，第 (i) 行第 (j) 列表示从点 (i) 到点 (j) 的最短距离：

• 若 (i=j)，输出 0；
• 若从 (i) 到 (j) 不可达，输出 INF；
• 否则输出最短距离值。 每行元素用一个空格分隔。

样例

3 4
1 2 2
1 3 5
2 3 1
3 1 7

0 2 3
8 0 1
7 9 0