#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;
	int cost;
	NOD* next;

};

NOD* L[MAX];

int d[MAX],h[MAX],viz[MAX];

int n,m,lh;

void date();

void push(int);

int pop(int);

void add(NOD*&,int,int);

void dijkstra();

void afisare();

int main(){

	date();
	dijkstra();
	afisare();
	return 0;

}

void add(NOD*& p,int nd, int ct){
	
	NOD* q=new NOD;
	q->next=p;
	q->nod=nd;
	q->cost=ct;
	p=q;

}


void push(int x){

	int fiu=++lh;
	int tata=fiu>>1;

	while(fiu && d[h[tata]]>d[x]) { 
		h[fiu]=h[tata];
		fiu=tata;
		tata>>=2;
	}
	h[fiu]=x;
			
}

int pop(){

	int min = h[1];

	h[1] = h[lh--];

	int tata=1, fiu=2*tata;

	while(fiu<=lh){

		if(fiu<lh) if(d[h[fiu]]>d[h[fiu+1]]) fiu++;
		
		if(d[1]>=d[h[fiu]]){

			h[tata]=h[fiu];
			tata=fiu;
			fiu<<=1;

		}else fiu=lh+1;
	}

	h[tata]=h[1];

	return min;
}


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

	for(i=1;i<=m;i++) {fscanf(f,"%d%d%d",&x,&y,&c);add(L[x],y,c);}

	for(i=1;i<=n;i++){ d[i]=INF;viz[i]=0;}

}


void dijkstra(){
	int min;
	int start=1;NOD* q=new NOD;

	push(start);d[start]=0;viz[start]=1;

	for(;lh;){

		min=pop();
		q=L[min];
		viz[min]=1;

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

			if(!viz[q->nod] && d[q->nod]>d[min] + q->cost) {

				d[q->nod] = d[min] + q->cost; push(q->nod);



			}
	}
}

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

}