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

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

struct NOD {

	long nod;
	long cost;
	NOD* next;

};

NOD* L[MAX];

long d[MAX],pre[MAX],h[MAX], viz[MAX];

long n,m,lh;

void date();

void push(long);

long pop(long);

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

void dijkstra();

void afisare();

int main(){

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

}

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

}


void push(long x){

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

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

long pop(){

	long min = h[1];

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

	long 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(){
	long i;
	fscanf(f,"%ld%ld",&n,&m);
	long x,y,c;
	
	for(i=1;i<=m;i++) {fscanf(f,"%ld%ld%ld",&x,&y,&c);add(L[x],y,c);}

	for(i=1;i<=n;i++) d[i]=INF;

}


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

	push(start);d[start]=0;viz[1]=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; pre[q->nod] = min; push(q->nod);}
	}    
}

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

}