题目描述

给定一张有 $n$ 个顶点、$m$ 条边的无向连通图。对每一个有序点对 $(i,j)$，求从顶点 $i$ 到顶点 $j$ 的最短路径长度。

输入格式

首行给出两个整数 $n,m$，分别为顶点数与边数。

随后 $m$ 行，每行的三个整数 $u,v,w$ 表示顶点 $u$ 和 $v$ 间有一条权值为 $w$ 的无向边。

输出格式

输出 $n$ 行，每行 $n$ 个整数。第 $i$ 行第 $j$ 个数是从顶点 $i$ 到顶点 $j$ 的最短距离。

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

说明/提示

$1\le n\le100$，$m\le4500$，$1\le u,v\le n$，$1\le w\le1000$。图连通，可能存在重边。 任意两点之间都存在路径。边权为正整数，同一对顶点之间可能有多条边。