#include <iostream>
#include <fstream>
#include <map>
#include <queue>

using namespace std;

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

typedef pair<int, int> P;

// Reutrn distance from node 1 to each of other nodes.
void Dijkstra(map<int, vector<pair<int, int>>> &graph,
              const int& n, vector<int>* result) {
  result->clear();
  result->resize(n + 1);
  priority_queue<P, vector<P>, greater<P>> heap;
  heap.push(make_pair(0, 1));
  map<int, bool> visited;
  while (!heap.empty()) {
    const auto p = heap.top();
    heap.pop();
    const int& cost = p.first;
    const int& node = p.second;
    if (visited[node]) {
      continue;
    }
    visited[node] = true;
    (*result)[node] = cost;
    for (const auto& edge : graph[node]) {
      const int& neighbour = edge.first;
      const int& edge_cost = edge.second;
      if (visited[neighbour]) {
        continue;
      }
      heap.push(make_pair(cost + edge_cost, neighbour));
    }
  }
}

int main (int argc, char const *argv[]) {
  int n, m;
  in>>n>>m;
  map<int, vector<P>> graph;
  for (int i = 0; i < m; ++i) {
    int x, y, c;
    in>>x>>y>>c;
    graph[x].push_back(make_pair(y, c));
  }
  vector<int> result;
  Dijkstra(graph, n, &result);
  for (int i = 2; i <= n; ++i) {
    out<<result[i]<< " ";
  }
  return 0;
}