#include<bits/stdc++.h>
using namespace std;
int dis[210][210];
int main() {
	int n, m;
	cin >> n >> m;
	memset(dis, 0x3f, sizeof(dis));
	for (int i = 1; i <= m; i ++) {
		int x, y, z;
		cin >> x >> y >> z;
		dis[x][y] = z;
		dis[y][x] = z;
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			for (int k = 1; k <= n; k ++) {
				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 ++) {
			if (i != j) cout << dis[i][j] << " ";
			else cout << 0 << " ";
		}
		cout << endl;
	}
	return 0;
}