描述

我们已经学习了图是什么了，现在试着让计算机记住你给出的图，试着将一个包含 n 个节点与 m 条边的图存储下来吧。

输入格式

第一行包含两个整数 n , m , 表示图有 n 个节点和 m 条边。

接下来 m 行，每行包含三个整数 u , v , w , 表示一条从 u 连向 v 的边的长度为 w。

输出格式

输出共 n 行，每行有 n 个整数。 第 u 行第 v 列的数表示从节点 u 到节点 v 的边长。（若边不存在则输出-1）

样例

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

-1 1 3 2 -1
-1 -1 -1 1 -1
-1 -1 -1 -1 2
-1 -1 -1 -1 4
-1 5 -1 -1 -1

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

-1 2 5 4
-1 -1 2 1
-1 -1 -1 3
-1 -1 -1 -1