#include <stdio.h>
#include <stdlib.h>
#define MAXN 50001
#define MAXM 250001
#define father(x) (x/2)
#define leftson(x) (2*x)
#define rightson(x) (2*x+1)

struct nod{
  int val, ph, viz;
} node[MAXN];

int lst[MAXN], vf[MAXM], next[MAXM], c[MAXM], m;

void add(int x, int y, int cost){
  vf[++m]=y; c[m]=cost;
  next[m]=lst[x];
  lst[x]=m;
}

int heap[MAXN+1], h;

void swp(int i, int j){
  int aux=node[heap[i]].ph; node[heap[i]].ph=node[heap[j]].ph; node[heap[j]].ph=aux;
  aux=heap[i]; heap[i]=heap[j]; heap[j]=aux;
}

void up(int pos){
  while(father(pos) && node[heap[pos]].val<node[heap[father(pos)]].val){
    swp(pos, father(pos));
    pos=father(pos);
  }
}

void down(int pos){
  int son;
  do{
    son=0;
    if(leftson(pos)<=h)
      son=leftson(pos);
    if(rightson(pos)<=h && node[heap[leftson(pos)]].val>node[heap[rightson(pos)]].val)
      son=rightson(pos);
    if(son)
      if(node[heap[pos]].val<=node[heap[son]].val)
        son=0;
      else{
        swp(pos, son);
        pos=son;
      }
  } while(son);
}

int main()
{
    FILE *fin, *fout;
    int n, M, i, x, y, z, p;
    fin=fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &M);
    for(i=0; i<M; i++){
      fscanf(fin, "%d%d%d", &x, &y, &z);
      add(x, y, z);
    }
    fclose(fin);
    heap[1]=node[1].ph=node[1].viz=h=1;
    while(h){
      p=lst[heap[1]];
      while(p){
        if(node[vf[p]].viz==0){
          node[vf[p]].viz=1;
          node[vf[p]].val=node[heap[1]].val+c[p];
          heap[++h]=vf[p];
          node[vf[p]].ph=h;
          up(h);
        } else if(node[vf[p]].val>node[heap[1]].val+c[p]){
          node[vf[p]].val=node[heap[1]].val+c[p];
          up(node[vf[p]].ph);
        }
        p=next[p];
      }
      swp(1, h);
      --h;
      down(1);
    }
    fout=fopen("dijkstra.out", "w");
    for(i=2; i<=n; i++)
      fprintf(fout, "%d ", node[i].val);
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}