#include<iostream.h>
#include<fstream.h>
#define inf 100000
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int s[50001],d[50001],t[50001],n,m,r=1,pos,a[20001][20001];
void init()
{
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j)
				a[i][j]=inf;
}
void init2()
{
	for(int i=1;i<=n;i++)
		{
		d[i]=a[r][i];
		if(i!=r&&a[r][i]<inf)
			t[i]=r;
		}
		s[r]=1;
}
void citire()
{
	f>>n>>m;
	init();
	int x,y,c;
	for(int i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		a[x][y]=c;
	}
	init2();
	f.close();
}
void drum(int k)
{
	if(t[k]!=0)
		drum(t[k]);
	cout<<k<<" ";
}
void dijkstra(int r)
{
	for(int i=1;i<n;i++)
	{
		int min=inf;
		for(int j=1;j<=n;j++)
			if(s[j]==0&&d[j]<min)
			{
				min=d[j];
				pos=j;
			}
			s[pos]=1;
		for(int j=1;j<=n;j++)
			if(s[j]==0&&d[j]>d[pos]+a[pos][j])
			{
				d[j]=d[pos]+a[pos][j];
				t[j]=pos;
			}
	}
}
int main()
{
	citire();
	dijkstra(r);
	for(int i=2;i<=n;i++)
		g<<d[i]<<" ";
}