#include<bits/stdc++.h>
#define inf 0x3f3f
using namespace std;
int n,m,w[114][114];
int main()
{
	memset(w,sizeof(w),inf);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int uin,vin,win;
		scanf("%d%d%d",&uin,&vin,&win);
		if(!w[uin][vin]) w[uin][vin]=inf;
		if(!w[vin][uin]) w[vin][uin]=inf;
		w[uin][vin]=min(w[uin][vin],win);
		w[vin][uin]=min(w[vin][uin],win);
	}
	/*for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			printf("%d ",w[i][j]);
		}
		printf("\n");
	}
	putchar('\n');*/
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i==j) w[i][j]=0;
				else
				{	
					if(w[i][k]!=inf&&w[k][j]!=inf)w[i][j]=min(w[i][j],w[i][k]+w[k][j]);
				}
				//if(w[i][j]<inf) printf("%d ",w[i][j]);
				//else printf("0 ");
			}
			//printf("\n");
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(w[i][j]<inf) printf("%d ",w[i][j]);
			else printf("INF ");
		}
		printf("\n");
	}
	return 0;
}