#include<cstdio>
#include<vector>
#include<utility>
using namespace std;
vector<pair<int,int> > V[50001];
int n,m,h[50001],p[50001],viz[50001],d[50001],oo,L;
void read(),solve(),hd(int),hu(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;
	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;
			hu(p[it->first]);
		}
	}
	for(i=2;i<=n;i++)
		d[i]==oo?printf("0 "):printf("%d ",d[i]);
}
void hu(int F)
{
	int T=F>>1,aux;
	if(!T)return;
	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;
	hu(T);
}
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);
	}
}