#include<stdio.h>
#define dim 50010
#define inf 2000000000
FILE*f=fopen("dijkstra.in","r");
FILE*g=fopen("dijkstra.out","w");

int min,p_min,n,m,a,b,i,Fr[dim],d,dist[dim],P[dim];
int dh;
struct heap{
	int v;
	int nr;
}H[dim],aux;

struct nod{
	int nr;
	int d;
	nod *adr;
}*L[250010],*p;

void up(int x){
	int c=x;
	int p=x/2;
	while(p){
		if(H[p].v>H[c].v){
			aux=H[p];
			H[p]=H[c];
			H[c]=aux;
			P[H[p].nr]=p;
			P[H[c].nr]=c;
			c=p;
			p=p/2;
		}
		else
			break;
	}
}

void down(int x){
	int c=2*x,p=x;
	while(c<=dh){
		if((c+1)<=dh&&H[c+1].v<H[c].v)
			c++;
		if(H[p].v>H[c].v){
			aux=H[p];
			H[p]=H[c];
			H[c]=aux;
			P[H[p].nr]=p;
			P[H[c].nr]=c;
			p=c;
			c=2*p;
		}
		else
			break;
	}
}

int main(){
	nod *c;
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&a,&b,&d);
		p=new nod;
		p->nr=b;
		p->d=d;
		p->adr=L[a];
		L[a]=p;
	}
	m=n;
	dh++;H[1].nr=1;
	while(dh){
		min=H[1].v;
		p_min=H[1].nr;
		H[1]=H[dh];
		dh--;
		down(1);
		dist[p_min]=min;
		c=L[p_min];
		while(c){
			if(!P[c->nr]){
				H[++dh].v=min+c->d;
				H[dh].nr=c->nr;
				P[c->nr]=dh;
				up(dh);
			}
			else{
				if(H[P[c->nr]].v>(min+c->d)){
					H[P[c->nr]].v=min+c->d;
					down(P[c->nr]);
				}
			}
			c=(c->adr);
		}
	}
	
	for(i=2;i<=n;i++)
		fprintf(g,"%d ",dist[i]);
	return 0;
}