#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,where,cat;
int minim,p;
int dest[50011],mymin[50011];
int d[50011]; //first=cost,second=dest
vector< pair<int,int> > a[50011]; //first=dest,second=cost

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

void upheap(int x,int p){
	int t;
	t=p>>1;
	while(p>1 && mymin[x]<mymin[d[t]]){
		    d[p]=d[t];
			dest[d[t]]=p;
			p=t;t=t>>1;		
		
	  	}
	d[p]=x;dest[x]=p;
}

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=2;i<=n;i++){
	mymin[i]=inf;
}

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

//rezolvare Nlog(N)
while (heapn){
    p=d[1];
		//stergem primul element si reactualizam heapul
	d[1]=d[heapn];
	dest[d[heapn]]=1;
	heapn--;
	downheap(1,heapn);
	//salvam costul minim pentru nodul eliminat
	               
 //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
	  where=a[p][i].first;
      cat=a[p][i].second;
	  if(mymin[p] + cat< mymin[where] ){
		  //daca vecinul exista in heap
		     mymin[where]=mymin[p]+cat;
		  //daca nu, il adaugam
		if(dest[where]==0){
			heapn++;
            upheap(where,heapn);
		}
     else
		upheap(where,dest[where]);
	  }
}
}


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