#include<fstream>
#include<iostream>
#include<set>
#include<vector>
using namespace std;

const int64_t MAX_VAL = (int64_t) 5 * 1000 * 1000 * 1000 + 1;

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

  int n, m;
  fin >> n >> m;

  vector <vector <pair <int, int>>> nei (n, vector <pair <int, int>>());
  for (int i = 0; i < m; i++) {
    int a, b, c;
    fin >> a >> b >> c;
    nei[a - 1].push_back({b - 1, c});
  }

  set <pair <int64_t, int>> cost_with_node;
  vector <int64_t> node_cost(n);
  cost_with_node.insert({0, 0});
  node_cost[0] = 0;

  for (int i = 1; i < n; i++) {
    cost_with_node.insert({MAX_VAL, i});
    node_cost[i] = MAX_VAL;
  }

  while (!cost_with_node.empty()) {
    auto rel_node = cost_with_node.begin();
    int64_t val = rel_node->first;
    int node = rel_node->second;
    cost_with_node.erase(rel_node);
    for (int i = 0; i < (int) nei[node].size(); i++) {
      int n_node = nei[node][i].first;
      int64_t n_val = node_cost[n_node];
      int64_t new_val = (int64_t) val + nei[node][i].second;
      if (new_val < n_val) {
        //delete the old cost
        auto it2 = cost_with_node.find({n_val, n_node});
        cost_with_node.erase(it2);
        //insert the new cost
        cost_with_node.insert({new_val, n_node});
        //update the value in vector
        node_cost[n_node] = new_val;
      }
    }
  }

  for (int i = 1; i < n; i++)
    fout << node_cost[i] << " ";
  fout << "\n";

  return 0;
}