#include <iostream>
#include <list>
#include <queue>
using namespace std;
list<int*> a[5000];
queue<int> q;
int vcost[5000];
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;
	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];
		else{
			int *x1;
			x1=(int*)malloc(8);
			x1[0]=-1,x1[1]=0;
			l.push_back(x1);
		}
		x[0]=nod2,x[1]=cost;
		l.push_back(x);
		a[nod1]=l;
		if(a[nod2].size()==0){
			list<int*> l1;
			int *x1;
			x1=(int*)malloc(8);
			x1[0]=-1,x1[1]=0;
			l1.push_back(x1);
			a[nod2]=l1;
		}
		(*next(a[nod2].begin(),0))[1]++;
		//cout<<nod2<<" "<<(*next(a[nod2].begin(),0))[1]<<endl;
		//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();
		int i=0;
		for(list<int*>::iterator it=l->begin();it!=l->end();){
			if(i==0){i++;it++;}
			else{
				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;
				(*next(a[(*it)[0]].begin(),0))[1]--;
				if((*next(l->begin(),0))[1]==0)
					l->erase(it++);
				else it++;
			}
		}
		
	}
	afiseaza();

}