#include <cstdio>
#include <list>

using namespace std;

const int inf=2000000000;
int n,m,d[50005],h[50005],k,inh[50005],poz[50005];
list<pair<int,int> > l[50005];
list<pair<int,int> >::iterator it;

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

void upheap(int nod,int pozitie){
	int fiu=pozitie,tata=pozitie/2;
	while(tata!=0 && d[h[tata]]>d[nod]){
		poz[h[tata]]=fiu;
		h[fiu]=h[tata];
		fiu=tata;
		tata=fiu>>2;
	}
	h[fiu]=nod;
	poz[h[fiu]]=fiu;
}	

void downheap(){
	h[1]=h[k];
	k--;
	int aux,min;
	int tata=1,fiu1=2,fiu2=3;
	while(fiu1<=k){
		if(fiu2>k)
			min=fiu1;
		else {
			if(d[h[fiu1]]>d[h[fiu2]])
				min=fiu2;
			else min=fiu1;
		}
		if(d[h[tata]]>d[h[min]]){
			poz[h[tata]]=min;
			poz[h[min]]=tata;
			aux=h[tata];
			h[tata]=h[min];
			h[min]=aux;
			tata=min;
		}
		else return;
		fiu1=tata<<1;
		fiu2=fiu1+1;
	}
}		
	

void dijkstra(){
	int i,nod;
	for(i=2;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	k=1;
	h[1]=1;
	inh[1]=1;
	while(k!=0){
		nod=h[1];
		inh[nod]=0;
		downheap();
		for(it=l[nod].begin();it!=l[nod].end();++it)
			if(d[(*it).first]>d[nod]+(*it).second){
				d[(*it).first]=d[nod]+(*it).second;
				if(inh[(*it).first]==1){
					upheap((*it).first,poz[(*it).first]);
				}
				else {
					inh[(*it).first]=1;
					k++;
					h[k]=(*it).first;
					upheap((*it).first,k);
				}
			}
	}				
}

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

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