#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <set>
using namespace std;

#define infinit 0x3f3f3f3f

typedef struct elem{
	int key,loc;
	void *val;
} *Elem;

typedef struct heap{
	int n,max;
	Elem *a;
} *PQ;

PQ PQ_New(){
	PQ h = (PQ) malloc (sizeof (struct heap));
	h->n = 0;
	h->max=100;
	h->a=(Elem*) malloc(100*sizeof(Elem));
	return h;
}

int PQ_Size(PQ h){
	return h->n;
}
int PQ_Empty(PQ h){
	return h->n == 0;
}
int PQ_Full(PQ h){
	return h->n == h->max;
}
Elem PQ_Min(PQ h){
	return h->a[0];
}

int FiltruJos(PQ h,int p,int n){
	int fiu,locf,locp;
	Elem t=h->a[p];
	for (;2*p+1<n;p=fiu){
		fiu = 2*p+1;
		if (fiu+1<n && h->a[fiu]->key>h->a[fiu+1]->key) fiu++;
		if (t->key<=h->a[fiu]->key) break;
		locf=h->a[fiu]->loc;
		locp=h->a[p]->loc;
		Elem aux = h->a[p];
		h->a[p]=h->a[fiu];
		h->a[p]->loc=locp;
		h->a[fiu]=aux;
		h->a[fiu]->loc=locf;
	}
	t->loc = p;
	return t->loc;
}
int FiltruSus(PQ h,int p){
	int tata=p,locp,loct;
	Elem t=h->a[p];
	while(p>0){
		tata=(p-1)/2;
		if (t->key >= h->a[tata]->key) break;
		loct=h->a[tata]->loc;
		locp=h->a[p]->loc;
		Elem aux = h->a[p];
		h->a[p]=h->a[tata];
		h->a[tata]=aux;
		h->a[tata]->loc=loct;
		h->a[p]->loc=locp;
		p=tata;
	}
	t->loc=p;
	return t->loc;
}

int PQ_Insert(PQ h, int k, void *v){
	Elem e;
	e=(Elem) malloc (sizeof (struct elem));
	e->key = k;
	e->val=v;
	e->loc = h->n;
	h->a[h->n] = e;
	h->n++;
	return FiltruSus(h,h->n-1);
}

Elem PQ_DelMin(PQ h){
	Elem t = h->a[0];
	h->a[0]=h->a[h->n-1];
	h->a[0]->loc=0;
	h->n--;
	FiltruJos(h,0,h->n);
	return t;
}

int PQ_ChPr(PQ h,int k,int p){
	int kv = h->a[p]->key;
	h->a[p]->key = k;
	if (kv < k)
		return FiltruJos(h,p,h->n);
	return FiltruSus(h,p);
}

void CrHeap(PQ h){
	int i;
	for (i=(h->n-2)/2;i>=0;i--)
		FiltruJos(h,i,h->n);
}

int *alocint(int x){
	int *p = (int *)malloc(sizeof(int));
	*p=x;
	return p;
}

typedef struct{
	int dist,parinte;
	vector<int> vecini;
}nod,*pnod;

typedef pnod *Graf;

int n,m,**cost,sursa=0;
Graf graf;
PQ h = PQ_New();

void Estimare(){
	for (int i = 0; i < n; i++){
		graf[i]->dist = infinit;
		graf[i]->parinte = -1;
		PQ_Insert(h,infinit,alocint(i));
	}
	graf[sursa]->dist = 0;
	PQ_ChPr(h,0,sursa);
}

void dijkstra(){
	Estimare();
	Elem e;
	int nod,vecin;
	vector<int>::iterator it;
	set<int> S;
	while(!PQ_Empty(h)){
		e = PQ_DelMin(h);
		nod = *(int*)e->val;
		S.insert(nod);
		for (it = graf[nod]->vecini.begin(); it != graf[nod]->vecini.end(); it++){
			vecin = *it;
			if (S.find(vecin) == S.end() && graf[vecin]->dist > graf[nod]->dist + cost[nod][vecin]){
				graf[vecin]->dist = graf[nod]->dist + cost[nod][vecin];
				graf[vecin]->parinte = nod;
				PQ_ChPr(h,graf[vecin]->dist,vecin);
			}
		}
	}
}

int main(){
	FILE *in,*out;
	in = fopen("dijkstra.in","r");
	out = fopen("dijkstra.out","w");
	fscanf(in,"%d%d",&n,&m);
	int s,d,c;
	
	graf = new pnod[n];

	cost = (int**)malloc(n*sizeof(int*));
	
	for (int i = 0; i < n; ++i){
		cost[i]=(int*)malloc(n*sizeof(int));
		graf[i] = new nod;
	}
	for (int i = 0; i < m; ++i){
		fscanf(in, "%d%d%d", &s,&d,&c);
		
		cost[s-1][d-1] = c;
		
		graf[s-1]->vecini.push_back(d-1);
		
	}
	dijkstra();
	for (int i = 1; i < n; ++i)
		if (graf[i]->dist != infinit)
			fprintf(out,"%d ",graf[i]->dist);
		else
			fprintf(out,"0 ");
	for (int i = 0; i < n; ++i){
		free(cost[i]);
		delete graf[i];
	}
	free(cost);
	delete graf;
	fclose(in);
	fclose(out);
	return 0;
}