#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,j,heapn;
int minim,p;
int s[50001],dest[50001],mymin[50001];
int 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));
	}


//d=inf,mymin=inf,dest=0
for(i=0;i<=n;i++){
	mymin[i]=inf;
	dest[i]=0;
}

//d[i] = distanta de la nod[1] la nod[i]
for(i=0;i<=(int)a[1].size()-1 ;i++){
	heapn++;
	d[heapn]=a[1][i].first;
	mymin[a[1][i].first]=a[1][i].second;
	dest[a[1][i].first]=heapn;
	upheap(heapn);
}

//selectam primul nod
s[1]=1;

//rezolvare Nlog(N)
while(heapn){
    p=d[1];
	int cost=mymin[d[1]];
	//stergem primul element si reactualizam heapul
	d[1]=d[heapn];
	heapn--;
	dest[d[1]]=1;
	downheap(1);
	//salvam costul minim pentru nodul eliminat
	  if(mymin[p]>cost)
		  mymin[p]=cost;
                   
 s[p]=1;
 //minimul pana la toti vecinii
  for(i=0;i<=(int)a[p].size()-1;i++)
	  //daca vecinul nu a fost selectat si costul este mai mic
	  if(s[a[p][i].first]==0 && cost +a[p][i].second < mymin[a[p][i].first] ){
		  //daca vecinul nu exista in heap, il adaugam
		  if(dest[a[p][i].first]==0) {
			   heapn++;
			   d[heapn]=a[p][i].first;
			   dest[a[p][i].first]=heapn;
			   upheap(heapn);
		  }	
		  mymin[a[p][i].first]=cost+a[p][i].second;
	  }
dest[p]=-1;
}


//afisam
for(i=2;i<=n;i++){
	if(mymin[i]!=inf)
	fprintf(g,"%d ",mymin[i]);
	else fprintf(g,"%d ",0);
}
return 0;
}