[1404]フロイド

#include <iostream>
#include <algorithm>
#define INF 100000000

using namespace std;

int main() {
	int n, m, mat[105][105] = { 0 };

	scanf("%d%*c%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) continue;
			mat[i][j] = INF;
		}
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		mat[a][b] = min(c, mat[a][b]);
	}
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			(mat[i][j] == INF) ? printf("0 ") : printf("%d ", mat[i][j]);
		}
		printf("\n");
	}
}