include <bits/stdc++.h>

using namespace std; const int inf = 10000000; int n, m; int a[1000][1000];

int main() {

cin >> n >> m;
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		if (i == j) {
			a[i][j] = 0;
		} else {
			a[i][j] = inf;
		}
	}
}
for (int i = 1; i <= m; i++) {
	int x, y, z;
	cin >> x >> y >> z;
	a[x][y] = z;
	a[y][x] = z;
}
for (int i = 1; i <= n; i++) {
	for (int k = 1; k <= n; k++) {
		for (int j = 1; j <= n; j++) {
			a[k][j] = min(a[k][j], a[k][i] + a[i][j]);
		}
	}
}
for (int i = 1; i <= n; i++) {
	for (int j = 1; j <= n; j++) {
		cout << a[i][j] << " ";
	}
	cout << endl;
}
return 0;

}