#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <climits>
#include <queue>
#include <map>

//using namespace std;

using ll = long long;

using ull = unsigned long long;

int T;

namespace Graph{
	
	int n , m;
	
	const int MAXN = 110;
	
	const int MAXM = 5000; 
	
	const int INF = 1e9 + 10;
	
	ll dis[MAXM][MAXM];
	
	void init(){
		
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= m;j++){
				
				if(i == j) dis[i][j] = 0;
				
				else dis[i][j] = INF;
			
			}
		
	}
	
	void read_and_min(){
		
		for(int i = 1 , u , v , w;i <= m;i++){
			
			std :: cin >> u >> v >> w;
			
			dis[u][v] = std :: min(dis[u][v] , (ll)w);
			
			dis[v][u] = std :: min(dis[v][u] , (ll)w);
			
		}
		
	}
	
	void awa(){
		
		for(int k = 1;k <= n;k++)
			for(int i = 1;i <= n;i++)
				for(int j = 1;j <= n;j++)
					if(dis[i][j] > dis[i][k] + dis[k][j])
						dis[i][j] = dis[i][k] + dis[k][j];
		
	}
	
	void readout(){
		
		for(int i = 1;i <= n;i++){
			
			for(int j = 1;j <= n;j++)
				std :: cout << dis[i][j] << ' ';
			
			std :: cout << '\n';
			
		}
		
	}
	
}

using namespace Graph;

void solve(){
	
	std :: cin >> n >> m;
	
	init();
	
	read_and_min();
	
	awa();
	
	readout();
	
}

signed main(){
	
	std :: ios::sync_with_stdio(false);
	
	std :: cin.tie(0);
	
	std :: cout.tie(0);
	
	T = 1;
	
	while(T--)
		solve();
	
	return (0 - 0);
}