#include<bits/stdc++.h>
using namespace std;

const int N = 110;

int n,m;

int g[N][N];

int dist[N][N];

bool s[N][N];

int dijkstra(){
	
    memset(dist, 0x3f, sizeof dist);
    for(int k = 1; k <= n; k++){
		dist[k][k] = 0;
		
    	for(int i = 1; i <= n; i ++){
        	int t = -1;
        
        	for(int j = 1; j <= n; j ++)
            	if(!s[k][j] && (t == -1 || dist[k][t] > dist[k][j]) )t = j;

        	s[k][t] = true;
        
        	for(int j = 1; j <= n; j ++){
            	dist[k][j] = min(dist[k][j], dist[k][t] + g[t][j]);
        }
    }
	}
    
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++)cout<<dist[i][j]<<" ";
        cout<<endl;    
    }
}

int main(){
    memset(g, 0x3f, sizeof g);
    
    cin>>n>>m;
    
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b], c);
        g[b][a] = min(g[b][a], c);
    }
    
    dijkstra();
    
    return 0;
    
}