/*
*	算法基本思想：
*		最开始只允许进过1号顶点进行中转，接下来只允许进过1和2号
*		顶点进行中转...，允许经过1~n号所有顶点进行中转，求任意两
*		点之间的最短路程。 
*
*	input   n=4,m=8 -->4个城市，8条公路 
*			t1 t2 t3 -->t1到t2需要t3的时间 
*			1  2  2
*			1  3  6
*			1  4  4
*			2  3  3
*			3  1  7
*			3  4  1
*			4  1  5
*			4  3  12
*			
*	起初	    --1---2---3---4---> 到达点 
*		    |   
*		   1| 0   2   6   4
*		   2| INF 0   3   INF
*		   3| 7   INF 0   1
*		   4| 5   INF 12  0 
*		    |
*		出发点 
*		
*	如果要让任意两点之间的路程变短，只能引入第三个点，并通过该点中
*	转，才可能缩短原来的两点距离。
*	
*	假设现在只允许经过1号顶点，求任意两点之间的最短路程。
*	方法：e[i][1] (从i到1)+ e[1][j](从1到j) _</>/=__ e[i][j] 
*		代码如下：
*		for(int i = 1;i<=n;i++){
*			for(int j = 1;j<=n;j++){
*				if(e[i][j])>e[i][1]+e[1][j])
*					e[i][j] = e[i][1]+e[1][j];
*			}
*		}
*允许过1后	    --1---2---3---4---> 到达点 
*		    |   
*		   1| 0   2   6   4
*		   2| INF 0   3   INF
*		   3| 7   9   0   1   	
*		   4| 5   7   11  0 
*		    |
*		出发点 	
*		修改:e[3][2] -->> 3-->1-->2
*			 e[4][2] -->> 4-->1-->2
*			 e[4][3] -->> 4-->1-->3 
*		
*	接着在可以进过1点的情况下允许经过2点，看看有没有可以再变短的
*	接着在进过1，2点的情况下允许经过3点，看看有没有可以再变短的
*	接着在进过1，2，3点的情况下允许经过4点，看看有没有可以再变短的
* 	所以 得出核心算法：
*		for(int k=1;k<=n;k++) //k代表中转点 
*			for(int i=1;i<=n;i++)
*				for(int j=1;j<=n;j++)
*					if(e[i][j]>e[i][k]+e[k][j])
* 						e[i][j] = e[i][k]+e[k][j];
*	  模拟：
*	  k=1:  1-->1
*	        1-->2 -->> 1-->1-->2
*	        ... //因为k与i都为1 所以就是直达的，没绕别点 
*	  k=2:  1-->2 -->> 1-->2-->1
*	        1-->2 -->> 1-->3-->2 //假设1-->2进过3,4两点后最短
*	        ... 
*	        ...
*	  i=3 k=4 j=2:
*	  	3-->2 -->> 3-->4-->2 
*	  
*	  所以最后 1--2 -->> 1-->3-->4-->2 
*	    	   
*/

#include <stdio.h>
int main(){
    int e[10][10]; //地图面积 
	int k,i,j;  //计数作用 
	int n,m,t1,t2,t3;
	//n表示顶点个数，m表示边的条数
	//t1,t2,t3 --> t1到t2需要t3的时间 
    int inf=99999999; 
	//用inf(infinity的缩写)存储一个我们认为的正无穷值
    
	//读入n和m，n表示顶点个数，m表示边的条数
    scanf("%d %d",&n,&m);
    
    //地图初始化
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i==j) 
		e[i][j]=0;  
            else 
		e[i][j]=inf;
 
    //读入边
    for(i=1;i<=m;i++){
        scanf("%d %d %d",&t1,&t2,&t3);
        e[t1][t2]=t3;
    }
    
    //Floyd-Warshall算法核心语句
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(e[i][j]>e[i][k]+e[k][j]) 
                	e[i][j]=e[i][k]+e[k][j];
    
    //输出最终的结果
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            printf("%10d",e[i][j]);
            //输出宽度为10的整数，不足补零 
        }
        printf("\n");
    }
    
    return 0;
}
/*
*	注意：
*		Floyd-Warshall算法不能解决带有"负权回路"的图，因为带有
*		"负权回路"的图没有最短路。 
*/