【题目描述】

求下图中任意两点之间的最短路经并输出。

输入格式

共m+1行，其中:第一行为整数n,m,分别表示图顶点数和边的个数。 第2行到第m+1行（共m行） ，每行三个整数x,y,w，分别表示相连的两个顶点和边的权值。

输出格式

n*n的矩阵，记录任意两点间最短路径。

6 9
1 2 6
1 3 3
2 3 12
2 4 5
3 4 3
3 5 4
4 5 2
4 6 3
5 6 5

 0 6 3 6 7 9
 6 0 8 5 7 8
 3 8 0 3 4 6
 6 5 3 0 2 3
 7 7 4 2 0 5
 9 8 6 3 5 0

数据范围

$1 < n,m <= 100$