#include <stdio.h>
#include <assert.h>

#define MAX_N 50000
#define MAX_M 250000
#define MAX_C 30000
#define NIL -1

typedef struct {
  int v, cost;
  int next;
} List;

typedef struct {
  int v;
  int next;
} Dial;

Dial c[3 * MAX_N];
int s[MAX_C];

List l[MAX_M];
int adj[MAX_N];

int d[MAX_N];

int st[MAX_N], ss;

void addEdge(int u, int v, int cost, int pos) {
  l[pos].v = v;
  l[pos].cost = cost;
  l[pos].next = adj[u];
  adj[u] = pos;
}

void emplaceList(int l, int v, int pos) {
  c[pos].v = v;
  c[pos].next = s[l];
  s[l] = pos;
}

int main(void) {
  FILE *fin = fopen("dijkstra.in", "r");
  FILE *fout = fopen("dijkstra.out", "w");
  int n, m, i, j, k;
  int u, v, cost;
  int ptr;

  fscanf( fin, "%d%d", &n, &m );

  for ( i = 0; i < MAX_C; i++ ) {
    s[i] = NIL;
  }
  adj[0] = NIL;
  d[0] = 0;
  emplaceList( 0, 0, 0 );
  for ( i = 1; i < n; i++ ) {
    adj[i] = NIL;
    d[i] = MAX_C - 1;
    emplaceList( MAX_C - 1, i, i );
  }

  for ( i = 0; i < m; i++ ) {
    fscanf( fin, "%d%d%d", &u, &v, &cost );
    addEdge( u - 1, v - 1, cost, i );
  }
  fclose( fin );

  ptr = n;
  for ( i = 0; i < MAX_C; i++ ) {
    for ( j = s[i]; j != NIL; j = c[j].next ) {
      u = c[j].v;
      for ( k = adj[u]; k != NIL; k = l[k].next ) {
        v = l[k].v;
        cost = i + l[k].cost;
        if ( d[v] > cost ) {
          if ( cost != i ) {
            emplaceList( cost, v, ptr++ );
          } else {
            st[ss++] = v;
          }
          d[v] = cost;
        }
      }
      while ( ss ) {
        u = st[--ss];
        for ( k = adj[u]; k != NIL; k = l[k].next ) {
          v = l[k].v;
          cost = i + l[k].cost;
          if ( d[v] > cost ) {
            if ( cost != i ) {
              emplaceList( cost, v, ptr++ );
            } else {
              st[ss++] = v;
            }
            d[v] = cost;
          }
        }
      }
    }
  }

  for ( i = 1; i < n; i++ ) {
    fprintf( fout, "%d ", d[i] & -(d[i] != MAX_C - 1) );
  }
  fclose( fout );
  return 0;
}