#include<fstream.h>

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int a[100][100],n,m,d[100],s[100],t[100];
const int INF=30000;
void cit()
{
	int i,j,c;
	fin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		if(i!=j)
				a[i][j]=INF;
	while(fin>>i>>j>>c)
		a[i][j]=c;
}
void tipar()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			fout<<a[i][j]<<" ";
		fout<<'\n';
	}
}
void dijkstra()
{
	int min,poz;
	int i,j;
	s[1]=1;
	for(i=1;i<=n;i++)
	{
		d[i]=a[1][i];
		if(i!=1)
			if(d[i]<INF)
				t[i]=1;
	//fout<<s[i]<<" ";
	}

	for(i=1;i<n;i++)
	{
		min=INF;
		//fout<<min<<'\n';
		for(j=1;j<=n;j++)
			if(s[j]==0)
			{
		//	fout<<j<<'\n';
				if(min>d[j])
				{
					min=d[j];
					poz=j;

				}
			}
			//	fout<<min<<" ";
		s[poz]=1;
		for(j=1;j<=n;j++  )
			if(s[j]==0)
			if(d[j]>d[poz]+a[poz][j])
			{	d[j]=d[poz]+a[poz][j];
				t[j]=poz;
			}
	}
}



int main()
{
	int i;
	cit();
	tipar();
	dijkstra();
	for(i=1;i<=n;i++)
	fout<<d[i]<<" ";

	return 0;
}