#include<stdio.h>
#include<stdlib.h>
#define NMAX 50001
#define INF 100000000

struct nod {
  int x,c;
  nod *next;
};

FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
nod* v[NMAX];
int q[NMAX],d[NMAX],p[NMAX],rasp[NMAX],sel[NMAX],k,l,m,n;

void adauga(int x,int y,int c) {
  nod *a=new nod;
  a->x=y;
  a->c=c;
  a->next=v[x];
  v[x]=a;
}

void citeste() {
  int i,x,y,c;
  fscanf(f,"%d%d",&n,&m);
  for(i=1;i<=n;i++) {
    d[i]=0;
    p[i]=0;
    sel[i]=0;
    v[i]=NULL;
  }
  for(i=0;i<m;i++) {
    fscanf(f,"%d%d%d",&x,&y,&c);
    adauga(x,y,c);
  }
  fclose(f);
}

void sw(int &x,int &y) {
  int z=x;
  x=y;
  y=z;
}

void swap(int x,int y) {
  p[q[x]]=y;
  p[q[y]]=x;
  sw(q[x],q[y]);
  sw(d[x],d[y]);
}

void upheap(int x) {
  int t;
  while(x>1) {
    t=x>>1;
    if(d[t]>d[x]) {
      swap(x,t);
      x=t;
    }
    else x=1;
  }
}

void downheap(int x) {
  int f=x;
  do {
    if(2*x<=k) if(d[2*x]<d[x]) f=2*x;
    if(2*x+1<=k) if(d[2*x+1]<d[f]) f=2*x+1;
    if(f!=x) { swap(x,f); x=f; }
    else f=k+1;
  } while(f<=k);
}

void addHeap(int qq,int dd) {
  q[++k]=qq;
  d[k]=dd;
  p[qq]=k;
  upheap(k);
}

void actualizeaza(int qq,int d1,int d2) {
  int dd=(d1<INF)?d1+d2:d2;
  if(!p[qq]) addHeap(qq,dd);
  else
   if(dd<d[p[qq]]) {
     d[p[qq]]=dd;
     upheap(p[qq]);
   }
}

void actualizeazaVecini(int qq) {
  nod *a=v[qq];
  int dd=d[p[qq]];
  while(a) {
    if(!sel[a->x]) actualizeaza(a->x,dd,a->c);
    a=a->next;
  }
}

int elHeap() {
  int el=q[1];
  sel[el]=1;
  rasp[el]=d[1];
  swap(k--,1);
  downheap(1);
  return el;
}

void scrie() {
  for(int i=2;i<=n;i++) fprintf(g,"%d ",rasp[i]);
  fclose(g);
}

int main() {
  citeste();
  k=0;
  sel[1]=1;
  d[0]=INF;
  actualizeazaVecini(1);
  while(k) actualizeazaVecini(elHeap());
  scrie();
  return 0;
}