#include<cstdio>
#include<vector>
#include<utility>
using namespace std;
vector<pair<int,int> > V[50010];
int n,m,h[50010],p[50010],viz[50010],d[50010],oo,L;
void read(),solve(),hd(int);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	int a,b,c;
	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()
{
	int i,dc,nc,F,T,aux;
	vector<pair<int,int> >::iterator it;
	oo=60000000;
	for(i=2;i<=n;i++){d[i]=oo;p[i]=h[i]=i;}p[1]=h[1]=1;L=n;
	for(;L&&d[h[1]]<oo;)
	{
		dc=d[h[1]];nc=h[1];viz[nc]=1;
		h[1]=h[L];p[h[1]]=1;L--;hd(1);
		for(it=V[nc].begin();it!=V[nc].end();it++)
		{
			if(viz[it->first])continue;
			if(d[it->first]<=dc+it->second)continue;
			d[it->first]=dc+it->second;
			for(F=p[it->first];;)
			{
				T=F>>1;
				if(!T)break;
				if(d[h[T]]<=d[h[F]])break;
				aux=h[T];h[T]=h[F];h[F]=aux;
				p[h[T]]=T;p[h[F]]=F;
				F=T;
			}
		}
	}
	for(i=2;i<=n;i++)
		d[i]==oo?printf("0 "):printf("%d ",d[i]);
}
void hd(int T)
{
	int F=T<<1,aux;
	if(F>L)return;
	if(F<L)if(d[h[F]]>d[h[F+1]])F++;
	if(d[h[T]]>d[h[F]])
	{
		aux=h[T];h[T]=h[F];h[F]=aux;
		p[h[T]]=T;p[h[F]]=F;
		hd(F);
	}
}