//bellman ford
/*
* daca la sfarsit am muchia (u,v) ai d[v]>d[u] + cost(u,v) atunci am ciclu de cost negativ. chestia asta nu folosesc aici
* 
* varianta cu coada
* 	bag in coada varful de start
* 	cat timp coada este nevida:
* 		scot din coada pe x
* 		iau muchiile (x,y), daca se pot relaxa le relaxez si daca y nu este in coada il bag in coada
* 			
* 	
*/
#include <cstdio>
using namespace std;
#define MAX 50050
#define INFINIT 2000000000
struct muchie{
	int cost, capat;
	muchie *next;
};
struct nod{
		int info;
		nod * next;
	};
muchie *a[MAX];
int d[MAX],n;

void read(){
	freopen("dijkstra.in","r",stdin);
	int i,j,cost,m;
	scanf("%d%d", &n,&m);
	muchie *p;
	for( ; m ;--m){
		scanf("%d%d%d", &i,&j,&cost);
		p = new muchie;
		p->capat = j;
		p->cost = cost;
		p->next = a[i];
		a[i] = p;
	}
}

void bellman_ford(int start){
	int inCoada[MAX];
	for(int i=1;i<=n;i++)
		d[i]=INFINIT, inCoada[i] = 0;;
	d[start]=0;
	nod *st, *dr,*tmp;
	int k;
	muchie *p;
	st=dr= new nod;
	st->info = start;
	inCoada[start] =1;
	st->next=NULL;
	while(st){
		k=st->info;
		inCoada[k] =0;
		for(p = a[k]; p ;p= p->next)
			if(d[p->capat] > d[k] + p->cost){
				d[p->capat] = d[k] + p->cost;
				if(!inCoada[p->capat]){
					tmp = new nod;
					tmp->info = p->capat;
					tmp->next = NULL;
					dr ->next = tmp;
					dr =tmp;
					inCoada[p->capat] =1;
				}
			}
		tmp=st;
		st = st->next;
		delete tmp;
	}
}

void write(){
	freopen("dijkstra.out","w",stdout);
	for(int i = 2 ; i<=n;i++)
		printf("%d ", d[i] == INFINIT ? 0 : d[i]);
}

int main(){
	read();
	bellman_ford(1);
	write();
	return 0;
}