#include <cstdio>
#include <vector>
#include <queue>
#include <cctype>

#define BUF_SIZE 1 << 12
const int INF = 2e9;
const int MAXN = 5e4;

struct Edge {
  int cost, dest;
  bool operator <(const Edge &aux) const {
    return cost > aux.cost;
  }
};

char buf[BUF_SIZE];
std::vector <Edge> g[MAXN + 1];
std::priority_queue <Edge> pq;
int d[MAXN + 1], pos = BUF_SIZE;

inline char getChar(FILE *f) {
  if (pos == BUF_SIZE) {
    fread(buf, 1, BUF_SIZE, f);
    pos = 0;
  }
  return buf[pos++];
}

inline int read(FILE *f) {
  int r = 0;
  char c;
  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    r = 10 * r + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return r;
}

int main() {
  int n, m, a, b, c, node, cost;
  FILE *f = fopen("dijkstra.in", "r");
  fscanf(f, "%d%d", &n, &m);
  for (int i = 0; i < m; ++i) {
    a = read(f), b = read(f), c = read(f);
    g[a].push_back({c, b});
  }
  fclose(f);
  for (int i = 0; i <= n; ++i) {
    d[i] = INF;
  }
  pq.push({0, 1});
  while (!pq.empty()) {
    node = pq.top().dest;
    cost = pq.top().cost;
    if (d[node] == INF) {
      d[node] = cost;
      for (int i = 0; i < g[node].size(); ++i) {
        if (d[g[node][i].dest] == INF) {
          pq.push({g[node][i].cost + cost, g[node][i].dest});
        }
      }
    }
    pq.pop();
  }
  f = fopen("dijkstra.out", "w");
  for (int i = 2; i <= n; ++i) {
    if (d[i] == INF) {
      fprintf(f, "0 ");
    } else {
      fprintf(f, "%d ", d[i]);
    }
  }
  fclose(f);
  return 0;
}