#include <stdio.h>
#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define INF 1<<30
#define MAX 50001

FILE *f=fopen(IN,"rt");
FILE *g=fopen(OUT,"wt");

struct NOD{

	int nod,cost;
	NOD *next;

};

NOD* L[MAX];
int d[MAX],poz[MAX],h[MAX];
int n,m,lh;

inline void swap(int&a, int &b){
	int aux;
	aux=a;a=b;b=aux;
}

inline void add(NOD*& p,int nd, int ct){

	NOD* q=new NOD;
	q->next = p;
	q->nod=nd;
	q->cost=ct;
	p=q;

}

void up(int x){
	int t;
	while(x){
		t = x>>1;
		if(d[h[t]] > d[h[x]]){

			poz[h[t]] = x;
			poz[h[x]] = t;
			swap(h[x],h[t]);
			x = t;
		}else return;
	}
}

void down(int x){
	int f;
	while(x<=lh){
	     f = x<<1;
	     if(f<=lh){
	      if(f+1<=lh)
	       if(d[h[f]]>d[h[f+1]]) f++;}
	     else return;
	     if(d[h[x]] > d[h[f]]){
		poz[h[x]]=f;
		poz[h[f]]=x;
		swap(h[f],h[x]);
		x=f;
	     }else return;
        }

}




void date(){
	int x,y,c,i;
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++) {

		fscanf(f,"%d%d%d",&x,&y,&c);
		add(L[x],y,c);
	}

}

void dijkstra(){
	int i;
	for(i=1;i<=n;i++) { d[i]=INF; poz[i]=-1;}
	int min;
	poz[1]=1;
	h[++lh]=1;
	d[1]=0;
	NOD *q=new NOD;

	for(;lh;){

		min = h[1];
		swap(h[1],h[lh--]);
		poz[h[1]]=1;
		down(1);

		q=L[min];


		for(;q;q=q->next){

			if(d[q->nod] > d[min] + q->cost){
				d[q->nod] = d[min] + q->cost;
				if(poz[q->nod]!=-1) up(poz[q->nod]);
				else{poz[q->nod]=++lh;h[lh]=q->nod;up(lh);}
			}
		}
	}
}


void afisare(){
	int i;
	for(i=2;i<=n;i++) fprintf(g,"%d ", d[i]==INF?0:d[i]);
}

int main(){
	date();
	dijkstra();
	afisare();
	return 0;
}