#include <iostream>
#include <list>
#include <stack>
using namespace std;
list<int*> a[50001];
stack<list<int*>> q;
int vcost[50001],n,m;
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(12);
		list<int*> l;
		scanf("%d %d %d",&nod1,&nod2,&cost);
		//cin>>nod1>>nod2>>cost;
		if(a[nod1].size()!=0)l=a[nod1];
		x[0]=nod2,x[1]=cost,x[2]=nod1;
		l.push_back(x);
		a[nod1]=l;
		//cout<<nod1<<" "<<nod2<<" "<<cost<<endl;
		//cout<<((int*)*next(a[nod1]->begin(),1))[0];		
	}
	q.push(a[1]);
	while(q.size()!=0){
		list<int*> l=q.top();
		q.pop();
		for(list<int*>::iterator it=l.begin();it!=l.end();){
			int c=vcost[(*it)[2]]+(*it)[1];
			int c1=vcost[(*it)[0]];
			if(c1==0)vcost[(*it)[0]]+=(*it)[1];
			else if(c<c1)vcost[(*it)[0]]=c;
			q.push(a[(*it)[0]]);
			l.erase(it++);
		}
	}
	for(int i=2;i<=n;i++){
		printf("%d ",vcost[i]);
	}
}