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

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

char buff[BUFFSIZE];
int pos = BUFFSIZE;

inline char GetChar(FILE *fin) {
  if ( pos == BUFFSIZE ) {
    fread( buff, 1, BUFFSIZE, fin );
    pos = 0;
  }
  return buff[ pos++ ];
}

inline int ReadInt(FILE *fin) {
  int q = 0;
  char c;

  do {
    c = GetChar(fin);
  } while ( !isdigit(c) );
  do {
    q = (10 * q) + (c - '0');
    c = GetChar(fin);
  } while ( isdigit(c) );
  return q;
}

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

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

Dial c[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 removeFromList(int l, int v) {
  int k = -1;
  if ( c[ s[l] ].v == v ) {
    k = s[l];
    s[l] = c[ s[l] ].next;
  } else {
    int i = s[l];
    while ( c[ c[i].next ].v != v ) {
      i = c[i].next;
    }
    k = c[i].next;
    c[i].next = c[ c[i].next ].next;
  }
  return k;
}

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;

  n = ReadInt(fin); m = ReadInt(fin);

  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++ ) {
    u = ReadInt(fin) - 1;
    v = ReadInt(fin) - 1;
    cost = ReadInt(fin);
    addEdge( u, v, 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 = i + l[k].cost;
        if ( d[v] > cost ) {
          if ( cost != i ) {
            emplaceList( cost, v, removeFromList( d[v], v ) );
          } else {
            removeFromList( d[v], v );
            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, removeFromList( d[v], v ) );
            } else {
              removeFromList( d[v], v );
              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;
}