#include <stdio.h>

#define oo 0x3f3f3f3f
#define maxn 50001

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

struct graf{
  int nod,cost;
  graf *adr_urm;
};

int n,m;
graf *a[maxn];

int d[maxn],h[maxn],poz[maxn],k;

void adauga(int where,int what,int cost){
  graf *p=new graf;
  p->cost=cost;
  p->nod=what;
  p->adr_urm=a[where];
  a[where]=p;
}

void citire(){
  fscanf(in,"%d%d",&n,&m);
  int a,b,c;
  while(m--){
    fscanf(in,"%d%d%d",&a,&b,&c);
    adauga(a,b,c);
  }
}

void swap(int a,int b){
  int aux;
  aux=h[a];
  h[a]=h[b];
  h[b]=aux;
  //  poz[h[a]]=a;
  //poz[h[b]]=b;

}

void downheap(int what){
  int son;
  while(son){
    son=0;
    if((what<<1)<=k){
      son=what<<1;
      if(son<k&&d[h[son+1]]<d[h[son]])son++;
      if(d[h[son]]>=d[h[what]])son=0;
    }
    if(son){
      swap(what,son);
      poz[h[what]]=what;
      poz[h[son]]=son;
      what=son; 
    }
  
  }
}

void upheap(int what){
  while(what>1&&(d[h[what]]<d[h[what>>1]])){
    swap(what,what>>1);
    poz[h[what]]=what;
    poz[h[what>>1]]=what>>1;
    what>>=1;
  }
  
}

void dijkstra_heap(){
  for(int i=2;i<=n;i++)d[i]=oo,poz[i]=-1;
  poz[1]=1;
  h[++k]=1;
  while(k){
    int min=h[1];
    swap(1,k);
    poz[h[1]]=1;
    k--;
    downheap(1);
    graf *q=a[min];
    while(q){
      if(d[q->nod]>d[min]+q->cost){
	d[q->nod]=d[min]+q->cost;
	if(poz[q->nod]!=-1)
	  upheap(poz[q->nod]);
	else{
	  h[++k]=q->nod;
	  poz[h[k]]=k;
	  upheap(k);
	}
      }
      q=q->adr_urm;
    }
}
}


int main(){
  citire();
  dijkstra_heap();
   for ( int i = 2; i <= n; ++i )    
    fprintf(out, "%d ", d[i] == oo ? 0 : d[i]);       fprintf(out, "\n");   
  fclose(in);
  fclose(out);
  return 0;
}