#include <stdio.h>
#include <stdlib.h>
#define MAXN 50000
#define MAXM 250000
#define NIL -1

int to[MAXM],d[MAXM],next[MAXM];
int heap[MAXN+1],toHeap[MAXN+1];

typedef struct Node{
  int d;
  int first;
}Node;

Node v[MAXN+1];

void sift_up(int i){
  int aux=heap[i];
  while(i>1&&v[aux].d<v[heap[i/2]].d){
    heap[i]=heap[i/2];
    i=i/2;
    toHeap[heap[i]]=i;
  }
  heap[i]=aux;
  toHeap[heap[i]]=i;
}

void sift_down(int i, int n){
  int aux,max,maxi;
  aux=heap[i];
  max=v[aux].d;
  maxi=i;

  if(i*2<=n&&v[heap[i*2]].d<max){
    max=v[heap[i*2]].d;
    maxi=i*2;
  }
  if(i*2+1<=n&&v[heap[i*2+1]].d<max){
    max=v[heap[i*2+1]].d;
    maxi=i*2+1;
  }

  while(maxi>i){
    toHeap[heap[i]]=i;
    heap[i]=heap[maxi];
    i=maxi;

    max=v[heap[i]].d;
    if(i*2<=n&&v[heap[i*2]].d<max){
      max=v[heap[i*2]].d;
      maxi=i*2;
    }
    if(i*2+1<=n&&v[heap[i*2+1]].d<max){
      max=v[heap[i*2+1]].d;
      maxi=i*2+1;
    }
  }

  heap[i]=aux;
  toHeap[heap[i]]=i;
}

int main()
{
    FILE *fin, *fout;
    int m,n,i,k,x,cell,y,z;
    fin=fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    k=0;
    for(i=1; i<=n; i++)
      v[i].d=v[i].first=NIL;
    for(i=0; i<m; i++){
      fscanf(fin, "%d%d%d", &x, &y, &z);
      to[k]=y;
      d[k]=z;
      next[k]=v[x].first;
      v[x].first=k;
      k++;
      /*
      to[k]=x;
      d[k]=z;
      next[k]=v[y].first;
      v[y].first=k;
      k++;
      */
    }
    v[1].d=0;
    heap[1]=1;
    k=1;
    while(heap[1]>=1){
      cell=v[heap[1]].first;
      while(cell!=NIL){
        if(v[to[cell]].d==NIL){
          heap[++k]=to[cell];
          v[to[cell]].d=v[heap[1]].d+d[cell];
          sift_up(k);
        }
        else if(v[heap[1]].d+d[cell]<v[to[cell]].d){
          v[to[cell]].d=v[heap[1]].d+d[cell];
          sift_up(toHeap[to[cell]]);
        }
        cell=next[cell];
      }

      heap[1]=heap[k];
      k--;
      sift_down(1, k);
    }

    fout=fopen("dijkstra.out", "w");
    for(i=2; i<=n; i++){
      if(v[i].d==NIL)
        fprintf(fout, "0 ");
      else
        fprintf(fout, "%d ", v[i].d);
    }
    fclose(fout);
    return 0;
}