// This program was written on 23.11.2021
// for problem dijkstra
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#define MAXN 50000
#define MAXM 250000
#define NIL  -1
#define INF  2000000000

int list[MAXN];
int adj[MAXM];
int cost[MAXM];
int next[MAXM];

int viz[MAXN];
int dist[MAXN];

int heap[MAXN];
int heappoz[MAXN];
int hn;

static inline void swap( int i, int j ){
  int aux;
  
  heappoz[heap[i]] = j;
  heappoz[heap[j]] = i;
  
  aux = heap[i];
  heap[i] = heap[j];
  heap[j] = aux;
}

static inline int minLRP( int i ){
  int c = 2 * i + 1, ret = i;
  
  if( c < hn && dist[heap[c]] < dist[heap[ret]] )
    ret = c;
  
  c++;
  
  if( c < hn && dist[heap[c]] < dist[heap[ret]] )
    ret = c;
  
  return ret;
}

void printHeap( int i, int indent ){
  int j;
  
  if( i >= hn )
    return;
  
  printHeap(i * 2 + 1, indent + 1);
  for( j = 0 ; j < indent ; j++ )
    fputs("  ", stdout);
  printf("%d\n", dist[heap[i]]);
  printHeap(i * 2 + 2, indent + 1);
}

static inline void fall( int i ){
  int next;
  
  while( (next = minLRP(i)) != i ){
    swap(i, next);
    i = next;
  }
}

static inline void rise( int i ){
  int next;
  
  while( dist[heap[next = ((i - 1) / 2)]] > dist[heap[i]] ){
    swap(i, next);
    i = next;
  }
}

static inline void init( int n ){
  int i;

  hn = 0;
  for( i = 0 ; i < n ; i++ ){
    dist[i] = INF;
    heappoz[i] = NIL;
    viz[i] = 0;
  }
}

static inline int pop(){
  int retval = heap[0];
  
  if( !hn ){
    //printf("  -> pop()\n");
    return NIL;
  }
  
  swap(0, --hn);
  fall(0);
  heappoz[retval] = NIL;
  
  //printf("  -> pop()\t\t-%d\n", retval);
  //printHeap(0, 15);
  return retval;
}

static inline void update( int node, int val ){
  //printf("  -> update(%d, %d)", node, val);
  if( heappoz[node] == NIL ){
    //printf("\t+%d", node);
    heappoz[node] = hn;
    heap[hn++] = node;
    dist[node] = val;
    rise(heappoz[node]);
  }else{
    dist[node] = val < dist[node] ? val : dist[node];
    rise(heappoz[node]);
  }
  //printf("\n");
  //printHeap(0, 15);
}

FILE *fin, *fout;

static inline int fgetint(){
  int n = 0, ch, semn = 1;

  while( isspace(ch = fgetc(fin)) );
  if( ch == '-' ){
    semn = -1;
    ch = fgetc(fin);
  }
  do
    n = n * 10 + ch - '0';
  while( isdigit(ch = fgetc(fin)) );

  return n * semn;
}

int main(){
  fin  = fopen("dijkstra.in",  "r");
  fout = fopen("dijkstra.out", "w");
  
  int n, m, i, node, a, b;
  
  n = fgetint();
  for( i = 0 ; i < n ; i++ )
    list[i] = NIL;
  
  m = fgetint();
  for( i = 0 ; i < m ; i++ ){
    a = fgetint() - 1;
    b = fgetint() - 1;
    
    next[i] = list[a];
    adj[i] = b;
    cost[i] = fgetint();
    list[a] = i;
  }
  
  init(n);
  
  update(0, 0);
  while( (node = pop()) != NIL ){
    //printf("@node = %d | dist = %d\n", node, dist[node]);
    viz[node] = 1;
    
    for( i = list[node] ; i != NIL ; i = next[i] )
      if( !viz[adj[i]] )
        update(adj[i], dist[node] + cost[i]);
  }

  for( i = 1 ; i < n ; i++ )
    fprintf(fout, "%d ", dist[i] == INF ? 0 : dist[i]);
  fputc('\n', fout);
  
  fclose(fin);
  fclose(fout);
  return 0;
}