RT

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1005;
int p[N][N];
int u,v,w;
int n,m;
int main() {
	cin >> n >> m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(i==j) p[i][j]=0;
			else p[i][j]=INF;
	for(int i=1; i<=m; i++) {
		cin >> u >> v >> w;
		p[u][v]=w;
		p[v][u]=w;
		p[v][u]=p[u][v]=min(w,p[v][u]);
	}
	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				if(p[i][j]>p[i][k]+p[k][j] )
					p[i][j]=p[i][k]+p[k][j];
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) 
			cout << p[i][j] << ' ';
		cout << endl;
	}
	return 0;
}