#include <iostream>
#include <list>
#include <queue>
using namespace std;
list<int*> a[50001];
struct x{
	list<int*>* a;
	int nod;
} p;
queue<x> q;
int vcost[50001];
int dg[50001];
int n,m;
void afiseaza(){
	for(int i=2;i<=n;i++){
		printf("%d ",vcost[i]);
	}
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int nod1,nod2,cost,ok=0;
	int* x;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		x=(int*)malloc(8);
		list<int*> l;
		scanf("%d %d %d",&nod1,&nod2,&cost);
		if(a[nod1].size()!=0)l=a[nod1];
		x[0]=nod2,x[1]=cost;
		l.push_back(x);
		a[nod1]=l;
		dg[nod2]++;
		//cout<<nod1<<" "<<nod2<<" "<<cost<<endl;
		//cout<<((int*)*next(a[nod1]->begin(),1))[0];		
	}
	p.a=&a[1];
	p.nod=1;
	q.push(p);
	while(q.size()!=0){
		list<int*> *l=q.front().a;
		int nod=q.front().nod;
		q.pop();
		for(list<int*>::iterator it=l->begin();it!=l->end();){
			int c=vcost[nod]+(*it)[1];
			int c1=vcost[(*it)[0]];
			if(c1==0||c<c1)vcost[(*it)[0]]=c;
			p.a=&a[(*it)[0]];
			p.nod=(*it)[0];
			q.push(p);
			//cout<<(*it)[2]<<endl;
			dg[(*it)[0]]--;
			if(dg[nod]==0)
				l->erase(it++);
			else it++;
		}
		
	}
	afiseaza();

}