#include<stdio.h>
#include<vector>
#define inf 2000000000

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

using namespace std;
int n,m,k,i,x,y,z,heapn,minim,p;
int s[50001],dest[50001],mymin[50001], d[50001];
vector< pair<int,int> > a[50001]; //first=dest,second=cost

void downheap(int p){
	int l,r;
	while(2*p<=heapn){
		minim=p;
		l=2*p;
		r=2*p+1;
		if( mymin[d[minim]] > mymin[d[l]] )
			 minim=l;
		if( r<=heapn && mymin[d[minim]] > mymin[d[r]] )
			 minim=r;
		if(minim!=p){
			dest[d[p]]=minim;
			dest[d[minim]]=p;
			 int t=d[p];
			     d[p]=d[minim];
			     d[minim]=t;
		}
		else break;
	}
}

void upheap(int p){
	int t;
	while(p>1){
		t=p/2;
		if(mymin[d[p]]<mymin[d[t]]){
			dest[d[p]]=t;
			dest[d[t]]=p;
			int m=d[p];
				d[p]=d[t];
				d[t]=m;
			p=t;
		}
	  else break;
	}
}

int main(){
//citire
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
	fscanf(f,"%d%d%d",&x,&y,&z);
	a[x].push_back(make_pair(y,z));
	}
for(i=0;i<=n;i++){
	mymin[i]=inf;
	dest[i]=0;
}
for(i=0;i<=(int)a[1].size()-1 ;i++){
	heapn++;
	d[heapn]=a[1][i].first;
	mymin[d[heapn]]=a[1][i].second;
	dest[d[heapn]]=heapn;
	upheap(heapn);
}
s[1]=1;
//***DIJKSTRA***//
while(heapn){
    p=d[1];
	int cost=mymin[d[1]];
	d[1]=d[heapn];
	heapn--;
	dest[d[1]]=1;
	downheap(1);
 s[p]=1;
  for(i=0;i<=(int)a[p].size()-1;i++)
	  if(s[a[p][i].first]==0 && cost +a[p][i].second < mymin[a[p][i].first] ){
		  mymin[a[p][i].first]=cost+a[p][i].second;
		  if(dest[a[p][i].first]==0) {
			   heapn++;
			   d[heapn]=a[p][i].first;
			   dest[d[heapn]]=heapn;
			   upheap(heapn);
		  }	
	  }
dest[p]=-1;
}
//***AFISARE***//
for(i=2;i<=n;i++){
	if(mymin[i]!=inf)
	fprintf(g,"%d ",mymin[i]);
	else fprintf(g,"%d ",0);
}
return 0;
}