#include<fstream.h>
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
const int inf=32000;
long m;
int a[5002][5002],n,viz[5002],min,d[5002];
void citire()
{
	f>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			a[i][j]=inf;
		a[i][i]=0;
	}
        int x,y,c;
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		a[x][y]=c;
	}
f.close();
}
void dij()
{
int x;
	for(int i=1;i<=n;i++)
	{
		d[i]=a[1][i];

	}
	viz[1]=1;
	for(i=2;i<=n;i++)
	{
		min=32000;
		for(int j=2;j<=n;j++)
		{
			if(min>d[j]&&viz[j]==0)
			{
				min=d[j];
				x=j;
			}
		}
		viz[x]=1;
		for(j=2;j<=n;j++)
		{
			if(viz[j]==0&&d[j]>d[x]+a[x][j])
			{
				d[j]=d[x]+a[x][j];
			}
		}
	}
}
int  main()
{
	citire();
	dij();
	for(int i=2;i<=n;i++)
	{
		g<<d[i]<<" ";
	}
g.close();
return 0;
}