2211 - 求任意两点之间的最短路

题目描述

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

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

输入

第一行两个整数 n, m

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

1 ≤ n ≤ 1001 ≤ 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
来源

图论

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 入门


上一题 下一题