#include<fstream.h>
#define INF 2500000

ofstream g("dijkstra.out");



int main()
{
	ifstream f("dijkstra.in");

	int i,a[5000][5000],s[5000],d[5000],x,y,z;
	int t[5000],n,m,j,nod,min,k,poz;

	f>>n>>m;
	nod=1;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=INF;

	for(i=1;i<=m;i++)
		{
			f>>x>>y>>z;
			a[x][y]=z;
		}

	s[nod]=1;
	for(i=1;i<=n;i++)
	{
		d[i]=a[nod][i];
		if(i!=nod&&d[i]<INF)
			t[i]=nod;
	}

	for(j=1;j<n;j++)
		{
		min=INF;
		for(k=1;k<=n;k++)
			if(s[k]==0&&d[k]<min)
				{
				min=d[k];
				poz=k;
				}
		s[poz]=1;
		for(k=1;k<=n;k++)
			if(s[k]==0&&d[poz]+a[poz][k]<d[k])
					{
					d[k]=d[poz]+a[poz][k];
					t[k]=poz;
					}
		}
	for(j=1;j<=n;j++)
		if(j!=nod)
			g<<d[j]<<" ";

return 0;
}