#include<stdio.h>
#include<algorithm>
#include<vector>
#define Nmax 50001
#define inf 1<<30
using namespace std;
int Poz,x,y,z,i,j,N,M,Nod,nr;
pair<int,int> Nod2;
vector <int> sol(Nmax),poz(Nmax),H(Nmax);
vector < pair<int,int> > a[Nmax];
vector < pair<int,int> >::iterator it;
void Swap(int a,int b)
{
	swap(H[a],H[b]);
	swap(poz[H[a]],poz[H[b]]);
}
void heap_up(int nod)
{
	while ( (nod>>1) && sol[H[nod>>1]]>sol[H[nod]] )
	{
		Swap(nod,nod>>1);
		nod>>=1;
	}
}
void heap_down(int nod)
{
	while ((nod<<1)<=nr)
	{
		if ((nod<<1)+1<=nr && sol[H[(nod<<1)+1]]<sol[H[nod<<1]] ) Poz=(nod<<1)+1;
			else Poz=(nod<<1);
		if (sol[H[nod]]<=sol[H[Poz]]) return;
		Swap(nod,Poz);
		nod=Poz;
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=M;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x].push_back(make_pair(y,z));
	}
	for (i=1;i<=N;++i)
	{
		H[++nr]=i;
		poz[i]=i;
		sol[i]=inf;
	}
	sol[1]=0;
	while (nr)
	{
		Nod=H[1];
		Swap(1,nr--);
		heap_down(1);
		for (it=a[Nod].begin();it!=a[Nod].end();++it)
			if (sol[Nod]+Nod2.second<sol[(*it).first])
			{
				sol[(*it).first]=sol[Nod]+(*it).second;
				heap_up(poz[(*it).first]);
			}
	}		
	for (i=2;i<=N;++i)
		printf("%d ",(sol[i]!=inf) ? sol[i]:0);
	return 0;
}