#include<bits/stdc++.h>
using namespace std;
int m,n,v2[105][105],u,v,w;
int main(){
	memset(v2,0x3f,sizeof(v2));
	cin>>m>>n;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(i==j)
				v2[i][j]=0;
	else
		v2[i][j]=0x3f;
	for(int i=1;i<=n;i++){
		cin>>u>>v>>w;
		v2[u][v]=w;
		v2[v][u]=w;
	}
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
				if(v2[i][k]+v2[k][j]<v2[i][j]){
					v2[i][j]=v2[i][k]+v2[k][j];
				} 
            }
        }
    }
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
    		cout<<v2[i][j];
		}
		cout<<endl;
	}
	return 0;
}