#include <stdio.h>
#define inf 100000000
FILE *f=fopen("dijkstra.in","rt");
FILE *g=fopen("dijkstra.out","wt");
long n,m;
struct nod{
	int cost,cine;
	nod* urm;
};

nod *v[50001];
int d[50001],viz[50001];

void date(void);
void add(int,int,int);
void dijkstra(void);

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

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

void add(int cn , int ct , int co){
	nod *p;
	p=new nod;
	p->cine = ct;
	p->urm=v[cn];
	p->cost=co;
	v[cn]=p;
}

void dijkstra(){
	for(long i=2;i<=n;i++) d[i]=inf;
	int min,k=0;
	for(i=1;i<=n;i++){
		min=inf;
		for(long j=1;j<=n;j++){
			if(d[j]<min && !viz[j]){min=d[j];k=j;}
		}
		viz[k]=1;
		nod* z;
		z=v[k];
		while(z){
			if(d[z->cine]>d[k]+z->cost) d[z->cine]=d[k]+z->cost;
			z=z->urm;
		}
	}
}