#include <cstdio>
#include <list>

using namespace std;

int n,m;
int d[50002],v[50002];

list<pair<int,int> > l[50002];
list<pair<int,int> >::iterator it;

void citire(){
	scanf("%d %d",&n,&m);
	int i,x,y,c;
	for(i=1;i<=m;i++){
		scanf("%d %d %d" , &x,&y,&c);
		l[x].push_back(make_pair(y,c));
	}
}

void dijkstra(int rad){
	int i,poz,min;
	for(i=1;i<=n;i++){
		d[i]=1000000000;
		v[i]=0;
	}
	d[rad]=0;
	while(1){
		min=1000000000;
		poz=0;
		for(i=1;i<=n;i++)
			if(v[i]==0 && d[i]<min){
				min=d[i];
				poz=i;
			}
		v[poz]=1;
		if(min==1000000000)
			break;
		for(it=l[poz].begin();it!=l[poz].end();++it)
			if(d[(*it).first]>d[poz]+(*it).second){
				d[(*it).first]=d[poz]+(*it).second;
			}
	}
}

void afisare(){
	int i;
	for(i=2;i<=n;i++)
		printf("%d ",d[i]);
	printf("\n");
}

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	afisare();
	return 0;
}