Description

给定一个 $n$ 点的有向图，求每两个点之间的最短路径。

若 $s$ 和 $t$ 不连通，输出 NO。 

Input Format

第一行一个整数 $n,m$ 分别表示点数，边数。

接下来 $m$ 行，每行三个整数 $u,v,w$ 分别表示一条边的起点，终点，边权。

Output Format

共 $n$ 行 $n$ 列，$a_{i,j}$ 表示从 $i$ 到 $j$ 的最短路径。

10 9
1 2 6772
1 3 -2244
1 4 -3936
4 5 -6732
5 6 -272
3 7 -4749
7 8 5971
7 9 -1723
6 10 -5950

0 6772 -2244 -3936 -10668 -10940 -6993 -1022 -8716 -16890 
NO 0 NO NO NO NO NO NO NO NO 
NO NO 0 NO NO NO -4749 1222 -6472 NO 
NO NO NO 0 -6732 -7004 NO NO NO -12954 
NO NO NO NO 0 -272 NO NO NO -6222 
NO NO NO NO NO 0 NO NO NO -5950 
NO NO NO NO NO NO 0 5971 -1723 NO 
NO NO NO NO NO NO NO 0 NO NO 
NO NO NO NO NO NO NO NO 0 NO 
NO NO NO NO NO NO NO NO NO 0

Hint

$1≤n≤10^2,-10^4≤w≤10^4$

Source

模板