题目描述

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

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

输入

第一行两个整数 $n$, $m$ ；

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

$1 ≤ n ≤ 100$ ， $1 ≤ m ≤ 5000$ ， $-1000 \le l \le 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

来源

图论