using namespace std;  
int n,m;  
int mapp[5000][5000];  
void floyd()  
{  
	for(int k=1;k<=n;k++)  
	{  
		for(int i=1;i<=n;i++)    
		{  
			for(int j=1;j<=n;j++)  
			{  
				if(i!=j && i!=k && j!=k && mapp[i][j]>mapp[i][k]+mapp[k][j])  
				{  
					mapp[i][j]=min(mapp[i][k]+mapp[k][j],mapp[i][j]);  
				}  
			}  
		}  
	}  
}  
int main()  
{  
	cin>>n>>m;  
	    memset(mapp,0x3f3f3f3f,sizeof(mapp));  
	for(int i=1;i<=m;i++)  
	{  
		int u,v,w;  
		cin>>u>>v>>w;  
		mapp[u][v]=w;  
		mapp[v][u]=w;  
	}  
	floyd();  
	for(int i=1;i<=n;i++)  
	{   
		for(int j=1;j<=n;j++)  
		{  
			if(mapp[i][j]==0x3f3f3f3f)cout<<0<<' ';  
			else cout<<mapp[i][j]<<' ';  
		}  
		cout<<endl;		  
	}  
		  
	return 0;  
}