题目描述

有一个有向图，有n个顶点m条边，请使用邻接矩阵存储这个图，并输出这个图的邻接矩阵。

如果如果两个点之间有多条边则邻接矩阵中只保存最短的边。如果两点之间没有边则输出999999999

输入输出格式

输入

第一行包含一个正整数 N 和 M； 接下来 M 行， 每行三个正整数 U、 V、 W， 表示该条道路为从 U 到 V 的， 且通过这条道路 需要 W 的时间。满足 1≤U,V≤N,1≤W≤10000, 输入保证任意两点都能互相到达。

输出

一个n*n的矩阵，矩阵的i行j列表示第i号城市和j号城市之间直接通路的时间。

Samples

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 -1
5 4 2

0 8 8 999999999 5 
999999999 0 5 999999999 999999999 
999999999 999999999 0 999999999 -1 
8 999999999 999999999 0 3 
999999999 999999999 4 2 0

限制

对于 30%的数据，满足 1≤N≤200。 对于 100%的数据，满足 1≤N≤1000,1≤M≤100000。