#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> dis(105, vector<int>(105, INT_MAX >> 3));
signed main(){
	scanf("%d%d", &n, &m);
	while(m--){
		int x, y, k;
		scanf("%d%d%d", &x, &y, &k);
		dis[x][y] = dis[y][x] = k;
		if(m <= n)
			dis[m][m] = 0;
	}for(int k = 1; k <= n; ++k){
		for(int i = 1; i <= n; ++i){
			for(int j = i; j <= n; ++j)
				dis[j][i] = dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
		}
	}for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= n; ++j)
			printf("%d ", dis[i][j]);
		printf("\n");
	}return 0;
}