#include<fstream>
#include<cstdio>
#include<vector>
#include<utility>
#define ff it->first
#define ss it->second

using namespace std;
int n,m,a,b,c,h[50010],poz[50010],i,l,nod;
long d[50005],oo=500000000,dist;
void read(),solve(),percolate(int t),sift(int f);
vector <pair<long,long> > v[50010];

int main()
{
	
	read();
	solve();
	return 0;
}
void read()
{
	ifstream in("dijkstra.in");
	in>>n>>m;
	for(;m;m--)
	{
		in>>a>>b>>c;
		v[a].push_back(make_pair(b,c));
	}
	in.close();
}
void solve()
{
	vector<pair<long,long> >::iterator it;
	ofstream out("dijkstra.out");
	for(i=1;i<=n;i++)
	{
		h[i]=0;
		d[i]=oo;
		poz[i]=0;
	}
	d[1]=0;
	l=1;
	h[1]=1;
	for(;l;)
	{
		nod=h[1];
		dist=d[nod];
		for(it=v[nod].begin();it!=v[nod].end();it++)
			if(d[ff]>dist+ss)
			{
				d[ff]=dist+ss;
				if(poz[ff]==0)
				{
					l++;
					h[l]=ff;
					percolate(l);
				}
				else percolate(poz[ff]);
			}
		h[1]=h[l];
		poz[h[1]]=1;
		l--;
		sift(1);
	}
	for(i=2;i<=n;i++)
	{
		if(d[i]==oo)
			d[i]=0;
	}
	for(i=2;i<=n;i++)
		out<<d[i]<<" ";
	out.close();
}
void percolate(int f)
{
	int t,aux;
	for(;;)
	{
		t=f>>1;
		if(d[h[t]]<=d[h[f]] || t<1)
			return;
		aux=h[t];
		h[t]=h[f];
		h[f]=aux;
		poz[h[t]]=t;
		poz[h[f]]=f;
		f=t;
	}
}
void sift(int t)
{
	int f,aux;
	for(;;)
	{
		f=t<<1;
		if(f>l)
			return;
		if(f<l)
			if(d[h[f]]>d[h[f+1]])
				f++;
		if(d[h[t]]<d[h[f]])
			return;
		aux=h[t];
		h[t]=h[f];
		h[f]=aux;
		poz[h[t]]=t;
		poz[h[f]]=f;
		t=f;
	}
}