#include <stdio.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[MAX_M];
int s[MAX_C];
int ptr;

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

int d[MAX_N];

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) {
  c[ptr].v = v;
  c[ptr].next = s[l];
  s[l] = ptr++;
}

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;

  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 );

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

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

  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 = d[u] + l[k].cost;
        if ( d[v] > cost ) {
          d[v] = cost;
          emplaceList( cost, v );
        }
      }
    }
  }

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