#include <stdio.h>

#define MAX_N 50000
#define MAX_M 250000
#define NIL -1
#define INF 1000000000

typedef struct {
  int v, d, next;
} cell;

cell l[MAX_M];
int adj[MAX_N];
int d[MAX_N];
int h[MAX_N];
int hpos[MAX_N];
int n, m;

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

int sift(int *size) {
  int ans = h[0];
  hpos[h[0]] = NIL;
  --(*size);
  h[0] = h[*size];
  hpos[h[*size]] = 0;

  int k = 0, best, changed;
  do {
    changed = 0;
    best = k;
    if ((2 * k + 1 < *size) && (d[h[2 * k + 1]] < d[h[best]])) {
      best = 2 * k + 1;
    }
    if ((2 * k + 2 < *size) && (d[h[2 * k + 2]] < d[h[best]])) {
      best = 2 * k + 2;
    }
    if (best != k) {
      hpos[h[k]] = best;
      hpos[h[best]] = k;
      int tmp = h[k];
      h[k] = h[best];
      h[best] = tmp;
      k = best;
      changed = 1;
    }
  } while (changed);
  return ans;
}

void percolate(int v) {
  int k = hpos[v];
  int p = (k - 1) / 2;
  while (k && (d[h[k]] < d[h[p]])) {
    hpos[h[k]] = p;
    hpos[h[p]] = k;
    int tmp = h[k];
    h[k] = h[p];
    h[p] = tmp;
    k = p;
    p = (k - 1) / 2;
  }
}

void dijkstra(int start) {
  for (int i = 0; i < n; i++) {
    d[i] = INF;
    h[i] = i;
    hpos[i] = i;
  }
  d[start] = 0;
  hpos[start] = 0;
  h[start] = 0;
  h[0] = start;
  hpos[0] = start;

  int hSize = n;
  while (hSize && (d[h[0]] < INF)) {
    int u = sift(&hSize);
    for (int p = adj[u]; p != NIL; p = l[p].next) {
      if (d[u] + l[p].d < d[l[p].v]) {
        d[l[p].v] = d[u] + l[p].d;
        percolate(l[p].v);
      }
    }
  }
}
int main (void) {
  FILE *f;
  int u, v, dist;

  f = fopen("dijkstra.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    adj[i] = NIL;
  }
  for (int i = 0; i < m; i++) {
    fscanf(f, "%d%d%d", &u, &v, &dist);
    addEdge(u - 1, v - 1, dist, i);
  }
  fclose(f);

  dijkstra(0);

  f = fopen("dijkstra.out", "w");
  for (int i = 1; i < n; i++) {
    if (d[i] < INF) {
      fprintf(f, "%d ", d[i]);
    } else {
      fputs("0 ", f);
    }
  }
  fclose(f);
  return 0;
}