【题目描述】 求下图中任意两点之间的最短路经并输出。

【输入样例格式】

共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