#include<fstream>
#include<vector>
#define dmax 50003
#define mult 10000000
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,cp[dmax],h[dmax];
bool t[dmax];
struct muchie
{	int v;
	int cs;
};
vector<struct muchie>g[dmax];
vector<struct muchie>::iterator it;
int left_son(int k)
{	return 2*k;
}
int right_son(int k)
{	return 2*k+1;
}
int father(int k)
{	return k/2;
}
void sift(int p,int k)
{	int x,s=0,tmp;
	do{	s=0;
		if(left_son(p)<=k)
		{	s=cp[left_son(p)];
			if(right_son(p)<=k)
				if(cp[h[right_son(p)]]<cp[h[s]])
					s=right_son(p);
		}
		if(cp[h[p]]<=cp[h[s]])
			s=0;	
		if(s)	
		{	tmp=h[p];
			h[p]=h[s];
			h[s]=tmp;
		}
	}while(s);
}
void percolate(int p,int k)
{	int f,v;
	v=p;
	while(cp[h[p]]<cp[h[father(p)]] && k>1)
	{	h[p]=h[father(p)];
		p=father(p);
	}	
	h[p]=v;
}
void update(int k)
{	int i;
	for(i=k/2;i>=1;i--)
		sift(i,k);
}
void dijkstra()
{	int i,r,bun;
	r=n-1;
	while(r)
	{	update(r);
		bun=h[1];
		t[bun]=1;
		h[1]=h[r];
		for(it=g[bun].begin();it<g[bun].end();it++)	
			if(!t[it->v])
				if(cp[it->v]>cp[bun]+it->cs)
					cp[it->v]=cp[bun]+it->cs;
		r--;
		percolate(1,r);	
	}		
}
int main()
{	int i,a,b,c;
	muchie q;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{	in>>a>>b>>c;
		q.v=b;
		q.cs=c;
		g[a].push_back(q);
	}
	in.close();
	for(it=g[1].begin();it<g[1].end();it++)
		cp[it->v]=it->cs;
	for(i=1;i<=n;i++)
	{	if(!cp[i])cp[i]=mult;
		h[i]=i+1;
	}
	t[1]=1;
	dijkstra();
	for(i=2;i<=n;i++)
	{	if(cp[i]==mult)
			cp[i]=0;
		out<<cp[i]<<" ";
	}	
	out.close();
	return 0;
}