using namespace std;
int dist[105][105],n,m;
int main()
{
	int u,v,w;
	memset(dist,0x3f,sizeof(dist));
	cin>>n>>m;
	for(int i=1;i<=n;i++)dist[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>w;
		dist[u][v]=dist[v][u]=w;
	}
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	for(int k=1;k<=n;k++)
	{
		if(i==j)continue;
		dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	}
	for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++)cout<<dist[i][j]<<" ";
	cout<<endl;}
	return 0;
}