#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#define NV it->first
#define DV it->second
using namespace std;
vector<pair<int,int> > v[50010];
void read(),solve(),HD(int T),HU(int F);
int n,m,A,B,C,L,D,N,d[50010],oo=500000000,h[50010],P[50010],i;
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d%d",&A,&B,&C);
		v[A].push_back(make_pair(B,C));
	}
}
void solve()
{
	vector<pair<int,int> >::iterator it;
	for(i=1;i<=n;i++){d[i]=oo;h[i]=i;P[i]=i;}
	d[1]=0;L=n;
	for(;L;)
	{
		N=h[1];D=d[N];//if(D==oo)break;
		for(it=v[N].begin();it!=v[N].end();it++)
			if(d[NV]>D+DV){d[NV]=D+DV;HU(P[NV]);}
		h[1]=h[L];P[h[1]]=1;L--;
		HD(1);
	}
	for(i=2;i<=n;i++)if(d[i]==oo)d[i]=0;
	for(i=2;i<=n;i++)printf("%d ",d[i]); 
}
void HU(int F)
{
	
	int T,aux;
	for(;;)
	{
		T=F>>1;
		if(d[h[T]]<=d[h[F]])return;
		aux=h[T];h[T]=h[F];h[F]=aux;
		P[h[T]]=T;P[h[F]]=F;
		F=T;
	}
}
void HD(int T)
{
	int F,aux;
	for(;;)
	{
		F=T<<1;
		if(F>L)return;
		if(F<L)
			if(d[h[F+1]]<d[h[F]])
				F++;
		if(d[h[T]]<=d[h[F]])return;
		aux=h[T];h[T]=h[F];h[F]=aux;
		P[h[T]]=T;P[h[F]]=F;
		T=F;
	}
}