#1194. 【模板】Floyd

【模板】Floyd

说明

给出一张由 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个点 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 条边组成的无向图。

求出所有点对 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo stretchy="false">)</mo></mrow></semantics></math>(i,j) 之间的最短路径。

输入格式

第一行为两个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>n,m,分别代表点的个数和边的条数。

接下来 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>m 行,每行三个整数 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>u,v,w,代表 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo separator="true">,</mo><mi>�</mi></mrow></semantics></math>u,v 之间存在一条边权为 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>w 的边。

输出格式

输出 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 行每行 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>n 个整数。

第 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>i 行的第 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>j 个整数代表从 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>i 到 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>j 的最短路径。

如果两点间不存在路径,输出-1

样例

4 4
1 2 1
2 3 1
3 4 1
4 1 1
0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0

提示

对于 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>100</mn><mi mathvariant="normal">%</mi></mrow></semantics></math>100% 的数据,<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>≤</mo><mn>100</mn></mrow></semantics></math>n100<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi><mo>≤</mo><mn>4500</mn></mrow></semantics></math>m4500,任意一条边的权值 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>�</mi></mrow></semantics></math>w 是正整数且 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn><mo>⩽</mo><mi>�</mi><mo>⩽</mo><mn>1000</mn></mrow></semantics></math>1w1000

数据中可能存在重边。