#include <cstdio>

const int MAXN = 5e4;
const int MAXM = 2e5 + MAXN;
#define father(x) ((x - 1) / 2)
#define leftson(x) (x * 2 + 1)
#define rightson(x) (x * 2 + 2)

int heap[MAXN + 1], poz[MAXN + 1], val[MAXM + 1],
    list[MAXN + 1], next[MAXM + 1], viz[MAXN + 1],
    cost[MAXM + 1], d[MAXN + 1], n, k;

inline void swap(int a, int b) {
  int aux;
  poz[heap[a]] = b;
  poz[heap[b]] = a;
  aux = heap[a];
  heap[a] = heap[b];
  heap[b] = aux;
}

inline void up(int p) {
  while ((p) && (d[heap[p]] < d[heap[father(p)]])) {
    swap(p, father(p));
    p = father(p);
  }
}

inline void down(int p) {
  int x;
  bool r;
  r = 0;
  while ((!r) && (leftson(p) < n)) {
    x = leftson(p);
    if ((rightson(p) < n) && (d[heap[rightson(p)]] < d[heap[x]])) {
      x = rightson(p);
    }
    if (d[heap[x]] < d[heap[p]]) {
      swap(p, x);
      p = x;
    } else {
      r = 1;
    }
  }
}

inline void add(int x, int y, int l) {
  cost[++k] = l;
  val[k] = y;
  next[k] = list[x];
  list[x] = k;
}

int main() {
  int cn, m, x, y, c, p;
  FILE *f = fopen("dijkstra.in", "r");
  fscanf(f, "%d%d", &n, &m);
  cn = n;
  k = 0;
  for (int i = 0; i < m; ++i) {
    fscanf(f, "%d%d%d", &x, &y, &c);
    add(x, y, c);
  }
  fclose(f);
  d[1] = poz[1] = 0;
  heap[0] = n = 1;
  while (n > 0) {
    p = list[heap[0]];
    while (p) {
      if (!viz[val[p]]) {
        viz[val[p]] = 1;
        d[val[p]] = d[heap[0]] + cost[p];
        heap[n] = val[p];
        poz[val[p]] = n;
        ++n;
        up(n - 1);
      } else if (d[val[p]] > d[heap[0]] + cost[p]) {
        d[val[p]] = d[heap[0]] + cost[p];
        up(poz[val[p]]);
      }
      p = next[p];
    }
    heap[0] = heap[--n];
    poz[heap[0]] = 0;
    down(0);
  }
  f = fopen("dijkstra.out", "w");
  for (int i = 2; i < cn; ++i) {
    fprintf(f, "%d ", d[i]);
  }
  fprintf(f, "%d\n", d[cn]);
  fclose(f);
  return 0;
}