题目描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环、自环）。

请编程计算出任意两点之间的最短路。

输入格式

第一行两个整数n, m；

接下来m行，每行有3个整数u、v、l，表示u点到v点之间有一条有向边，边长为l；

1 ≤ n ≤ 100，1 ≤ m ≤ 5000，-1000 <= l <= 1000。

注意：样例数据保证两点之间只有一条有向边。

输出格式

输出共n行，每行有n个整数，第i行的第j个数，代表的是从点i到点j的最短路的值；

如果两点之间不存在能达到的路径，请输出字母'N'；。

样例

3 3
1 2 -1
2 3 -1
3 1 2

0 -1 -2
1 0 -1
2 1 0