#include <stdio.h>
#define Nmax 50005
#define INF 2000000000

struct nod{
	int y,c;
   nod *urm;
} *a[Nmax];
int d[Nmax],poz[Nmax],h[Nmax];
int n,m,i,dh;

void read(){
	int i,x,y,c;
	freopen("dijkstra.in","r",stdin);
   freopen("dijkstra.out","w",stdout);
   scanf("%d%d",&n,&m);
   nod* aux;
   for(i=1;i<=m;++i){
   	scanf("%d%d%d",&x,&y,&c);
      aux = new nod;
      aux ->y =y;
      aux ->c =c;
      aux ->urm=a[x];
      a[x]=aux;
   }
   for(i=1;i<=n;++i){
   	d[i]=INF;
      h[i]=poz[i]=i;
   }
   d[1]=0;
   dh=n;
}

inline void swap(int i,int j){
	int aux=h[i];
   h[i]=h[j]; h[j]=aux;
   poz[h[i]]=i;
   poz[h[j]]=j;
}

void UP(int k){
	int tata=k/2;
   if( tata )
    if( d[h[k]]<d[h[tata]]){
		int aux=h[k];
  	   h[k]=h[tata]; h[tata]=aux;
  	   poz[h[k]]=k;
   	poz[h[tata]]=tata;

//   	swap(k,tata);
      UP(tata);
   }
}

void DOWN(int k){
	int st=2*k, dr=st+1, min=k;
   if( st<=dh && d[h[st]]<d[h[min]]) min=st;
   if( dr<=dh && d[h[dr]]<d[h[min]]) min=dr;
   if(min !=k){
		int aux=h[k];
   	h[k]=h[min]; h[min]=aux;
   	poz[h[k]]=k;
   	poz[h[min]]=min;

//   	swap(k,min);
      DOWN(min);
   }
}

void dijkstra(){
   int pmin; nod *p;

	while(dh){
      //scot min
   	int aux=h[1];
	   h[1]=h[dh]; h[dh]=aux;
   	poz[h[1]]=1;
   	poz[h[dh]]=dh;

//	   swap(1,dh);
   	dh--;
  	 	DOWN(1);
   	pmin= h[dh+1];

      for(p=a[pmin]; p; p=p->urm)
      	if(d[p->y] > d[pmin]+ p->c){
         	d[p->y] = d[pmin]+ p->c;
            UP(poz[p->y]);
         }
   }
}

void write(){
	int i;
   for(i=2;i<=n;++i)
     if(d[i]==INF) printf("%d ",0);
     else printf("%d ",d[i]);
   printf("\n");
   fclose(stdin); fclose(stdout);
}

int main(){
	read();
   dijkstra();
   write();
   return 0;
}