#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int INF = 1e9;
int n, m;
vector<vector<pair<int, int>>> graph;
vector<int> dist;

void citire() {
  fin >> n >> m;
  graph.resize(n + 1);
  dist.resize(n + 1, INF);
  dist[1] = 0;

  int x, y, cost;
  for (int i = 0; i < m; i++) {
    fin >> x >> y >> cost;
    graph[x].push_back({y, cost});
  }
}

void dijkstra() {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  pq.push({0, 1});

  while (!pq.empty()) {
    auto [d, node] = pq.top();
    pq.pop();

    if (d > dist[node])
      continue;

    for (auto &[neighbor, cost] : graph[node]) {
      if (dist[neighbor] > d + cost) {
        dist[neighbor] = d + cost;
        pq.push({dist[neighbor], neighbor});
      }
    }
  }
}

int main() {
  citire();
  dijkstra();
  for (int i = 2; i <= n; i++) {
    fout << (dist[i] == INF ? 0 : dist[i]) << " ";
  }
  cout << '\n';
  return 0;
}