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

const int INF = 2e9;
const int MAXN = 5e4;

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

std::vector <Edge> g[MAXN + 1];
std::priority_queue <Edge> pq;
int d[MAXN + 1];

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) {
    fscanf(f, "%d%d%d", &a, &b, &c);
    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;
}