#include<stdio.h>
#define N 50001
#define inf 1000000000

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

struct NOD{

	int nod,cost;
	NOD *next   ;
};

NOD * G[N];

int D[N],H[N],P[N];
int n,m,lh;

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

void ADD(NOD *& p, int who, int ct){

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

void up(int x){
	int t;
	while(x){
		t=x>>1;
		if(D[H[x]]<=D[H[t]]){
			swap(H[x],H[t]);
			P[H[x]]=t;
			P[H[t]]=x;
			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]]){
			swap(H[x],H[f]);
			P[H[x]]=f;
			P[H[f]]=x;
			x=f;
		}else return;
	}
}

void insert(int x){

	H[++lh]=x;
	P[H[lh]]=lh;
	up(lh);
}

void remove(){
	swap(H[1],H[lh--]);
	P[H[1]]=1;
	down(1);
}

void date(){

	fscanf(f,"%d%d",&n,&m);
	int x,y,c;
	for(; m-- ;){

		fscanf(f,"%d%d%d",&x,&y,&c);
		ADD(G[x],y,c);

	}

	for(x=1;x<=n;x++){ D[x]  = inf;P[x]=-1; }
}

void dijkstra(){

	int min;

	insert(1);
        D[1]=0;

	while( lh ){

		min = H[1];

        remove();

		NOD *q = new NOD;

		q=G[min];

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

		    if(D[q->nod] > D[min] + q->cost){
			D[q->nod] = D[min] + q->cost;
			if(P[q->nod]!=-1) up(P[q->nod]);
			else insert(q->nod);
		    }
		}
	}
}

int main(){

	date();
	dijkstra();
	for(int i=2;i<=n;i++) fprintf(g,"%d ",D[i]==inf?0:D[i]);
	return 0;
}