20pts

#include<bits/stdc++.h>
#pragma GCC optimeze(1)
#pragma GCC optimeze(2)
#pragma GCC optimeze(3,"Ofast","inline")
using namespace std;
int n,m,w[101][101],dis[101][101];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	memset(dis,114514,sizeof(dis));
	for(int i=1;i<=n;i++) {
		dis[i][i]=0;
	}
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++) {
		cin>>x>>y;
		cin>>w[x][y];
		w[y][x]=w[x][y];
		dis[x][y]=dis[y][x]=w[x][y];
	}
	for(int k=1;k<=n;k++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(i!=j&&j!=k&&i!=k&&dis[i][k]+dis[k][j]<dis[i][j]) {
					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<<0<<" ";
			}
			else {
				cout<<dis[i][j]<<" ";
			}
		}
		cout<<'\n';
	}
	return 0;
}