#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;
}

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 && d[h[k]]<d[h[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){
   	swap(k,min);
      DOWN(min);
   }
}

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

	while(dh){
      //scot min
	   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("0 ");
     else printf("%d ",d[i]);
   printf("\n");
   fclose(stdin); fclose(stdout);
}

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