#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define INPUT "dijkstra.in"
#define OUTPUT "dijkstra.out"
#define INFI 2000000000
#define CL(x) memset(x,0,sizeof(x));

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

typedef struct elem{
  long value,cost;
  struct elem *next;
};

elem* p[50001];

long n,m,cont;
long heap[50001],pozitie[50001],pozit2[50001],minim[50001];

void readValues();

void solveFunction();

void urcaHeap(long);

void coboaraHeap(long);

void schimba(long&,long&);

void printSolution();

int main(){
  readValues();
  solveFunction();
  fclose(fin);
  fclose(fout);
  return 0;
}

void readValues(){
  long val1,val2,val3;
  elem *adr;
  fscanf(fin, "%ld %ld", &n, &m);
  for(long i=1;i<=m;++i){
    fscanf(fin, "%ld %ld %ld", &val1, &val2, &val3);
    adr=new elem;
    adr->value=val2;
    adr->cost=val3;
    adr->next=p[val1];
    p[val1]=adr;
  }
}

void solveFunction(){
  long pozCur;
  int util[100];
  elem *adr;
  CL(util);
  for(long i=1;i<=n;++i)
    heap[i]=INFI;
  cont=0;
  adr=p[1];
  util[1]=1;
  while(adr!=NULL){
    util[adr->value]=1;
    heap[++cont]=adr->cost;
    pozitie[cont]=adr->value;
    pozit2[adr->value]=cont;
    urcaHeap(cont);
    adr=adr->next;
  }
  while(heap[1]!=INFI){
    pozCur=pozitie[1];
    minim[pozCur]=heap[1];
    pozit2[pozitie[1]]=0;
    heap[1]=heap[cont];
    heap[cont]=INFI;
    pozitie[1]=pozitie[cont];
    pozitie[cont]=0;
    pozit2[pozitie[1]]=1;
    --cont;
    coboaraHeap(1);
    adr=p[pozCur];
    while(adr!=NULL){
      if(util[adr->value]){
	if(minim[pozCur]+adr->cost<heap[pozit2[adr->value]]){
	  heap[pozit2[adr->value]]=minim[pozCur]+adr->cost;
	  urcaHeap(pozit2[adr->value]);
	}
      }
      else{
	heap[++cont]=minim[pozCur]+adr->cost;
	pozitie[cont]=adr->value;
	urcaHeap(cont);
	util[adr->value]=1;
      }
      adr=adr->next;
    }
  }
  printSolution();
}

void urcaHeap(long val){
  while(val>=1&&heap[val/2]>heap[val]){
    schimba(heap[val/2],heap[val]);
    schimba(pozitie[val/2],pozitie[val]);
    pozit2[pozitie[val/2]]=val/2;
    pozit2[pozitie[val]]=val;
    val/=2;
  }
}

void coboaraHeap(long val){
  while(val<cont&&(heap[2*val]<heap[val]||heap[2*val+1]<heap[val])){
  if(heap[2*val]<heap[2*val+1]&&2*val<cont){
    schimba(heap[2*val], heap[val]);
    schimba(pozitie[2*val], pozitie[val]);
    pozit2[pozitie[2*val]]=2*val;
    pozit2[pozitie[val]]=val;
    val*=2;
  }
  else
  if(heap[2*val]>heap[2*val+1]&&(2*val+1<cont)){
    schimba(heap[2*val+1], heap[val]);
    schimba(pozitie[2*val+1], pozitie[val]);
    pozit2[pozitie[2*val+1]]=2*val+1;
    pozit2[pozitie[val]]=val;
    val=2*val+1;
  }
  }
}

void schimba(long &val1, long &val2){
  val1=val1+val2;
  val2=val1-val2;
  val1=val1-val2;
}

void printSolution(){
  for(long i=2;i<=n;++i)
    fprintf(fout, "%ld ", minim[i]);
  fprintf(fout, "\n");
}