#include<fstream>
#include <string.h>
using namespace std;

	fstream fin("dijkstra.in",ios::in),fout("dijkstra.out",ios::out);

	int a[50][50],d[50],p[50],v[50],n,m,start,minim,infinit,pmin;
	void drum(int nod)
	{
		if(p[nod] !=0)
		{
			drum(p[nod]);
			fout<<nod<<" ";
		}
		else
		fout<<nod<<" ";
		return;
	}
	
	void pminim(int infinit, int &pmin)
	{
		int i;
		minim=infinit;
		for(i=1;i<=n;i++)
		{
			if(v[i]==0 && d[i]<minim)
			{
				minim=d[i];
				pmin=i;
			}
		}
		return ;
	}
int main()
{

	int i,x,y,k,c;
	fin>>n>>m;
	start=1;
	memset(a,5,sizeof(a));
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		a[x][y]=c;
	}
	
	infinit=a[0][0];
	for(i=1;i<=n;i++)
	{
		d[i]=a[start][i];
		if(d[i]!=infinit)
			p[i]=start;
	}
	
	d[start]=0;
	p[start]=0;
	v[start]=1;
	
	for(k=1;k<=n-1;k++)
	{
		pminim(infinit,pmin);
		if(pmin==0)
			break;
		v[pmin]=1;
		for(i=1;i<=n;i++)
		{
			if(d[i]>d[pmin]+a[pmin][i])
			{
				d[i]=d[pmin]+a[pmin][i];
				p[i]=pmin;
			}
		}
	}
	
	for(i=2;i<=n;i++)
	{
		fout<<d[i]<<" ";
	}
	
	



fin.close();
fout.close();
return 0;
}