#include <iostream>
#include <list>
#include <queue>
using namespace std;
list<int*> a[50001];
queue<int> q;
int vcost[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];		
	}
	q.push(1);
	while(q.size()!=0){
		int nod=q.front();
		list<int*> *l=&a[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;
			q.push((*it)[0]);
			//cout<<(*it)[2]<<endl;
			
				l->erase(it++);
			
		}
		
	}
	afiseaza();

}