#include<cstdio>
#include<vector>
using namespace std;
int n,m,d[50001],h[50001],poz[50001],x,y,c,i,vf;
const int lim=500000000;
struct mystruct{int first;int second;};
mystruct aux;
vector<mystruct> a[50001];

inline void change(int x,int y)
{
	int a;
	a=h[x];h[x]=h[y];h[y]=a;
	poz[h[x]]=x;poz[h[y]]=y;
}

void heapup(int i)
{
	if(i<=1) return;
	int t=(i>>1);
	if(d[h[i]]<d[h[t]]){
		change(i,t);
		heapup(t);}
}
void heapdown(int i)
{
	int st,dr,t=(i<<1);
	if(t<=m){
		st=h[t];
		if(t+1<=m) dr=h[t+1];
		else dr=st;
		if(d[dr]<d[st]) t=t+1;
		if(d[h[i]]>d[h[t]]){
			change(i,t);
			heapdown(t);}
	}
}

inline void build()
{
	for(i=1;i<=n;i++){
		h[i]=i;
		d[i]=lim;
		poz[i]=i;}
	d[1]=0;
}
inline int scoate()
{
	change(1,m);
	m--;
	heapdown(1);
	return h[m+1];
}
inline void dijkstra()
{
	m=n;
	build();
	while(m>0){
		vf=scoate();
		if(d[vf]==lim)break;
		x=a[vf].size();
		for(i=0;i<x;i++){
			y=a[vf][i].first;
			c=a[vf][i].second;
			if(d[y]>d[vf]+c){
				d[y]=d[vf]+c;
				heapup(poz[y]);}
		}
	}
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&c);
		aux.first=y;
		aux.second=c;
		a[x].push_back(aux);}
	dijkstra();
	for(i=2;i<=n;i++)
		if(d[i]<lim)printf("%d ",d[i]);
		else printf("0 ");
	fclose(stdout);
}