// Copyright 2018 Popescu Alexandru Gabriel <[email protected]>
// Copyright 2017 Darius Neatu <[email protected]>

// Dijkstra
// O(m log n)
// Deoarece folosesc heapuri binare (priority_queue),
// complexitatea este cea de mai sus

// http://www.infoarena.ro/problema/dijkstra

#include <bits/stdc++.h>

#define NMAX 50010   // ATENTIE la cat e in problema curenta !!!
#define oo (1 << 30) // ATENTIE la cat e in problema curenta !!!
#define NO_PARENT (-1)

using namespace std;

class Task {
public:
  void solve() {
    read_input();
    get_result();
    print_output();
  }

private:
  // n = vertices, m = edges
  int n, m;
  int source;

  // adj[i] contains pairs of neighbouring_node , weight of the edge
  // node -> neighbouring_node
  vector<pair<int, int>> adj[NMAX];

  // MinHeap containing: {distance from source to node x, node x}
  // Used to extract the node with the minimum estimated weight from source
  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 std::greater<pair<int, int>>> pq;

  // d[i] = minimum distance from source to node i
  vector<int> d;

  // p[i] = parent of i on the minimim road from source to i
  vector<int> p;

  void read_input() {
    ifstream fin ("dijkstra.in");
    cin >> n >> m;
    d.resize(n + 1);
    p.resize(n + 1);

    source = 1;

    for (int i = 1; i <= m; ++i) {
      int x, y, c;
      cin >> x >> y >> c;
      adj[x].push_back({y, c});
    }

    fin.close();
  }

  void get_result() { Dijkstra(source, d, p); }

  void Dijkstra(int source, vector<int> &d, vector<int> &p) {
    for (int i = 1; i <= n; ++i) {
      // Suppose there is not a way to reach node i
      d[i] = oo;
      // Neither is there a parent to the said node
      p[i] = NO_PARENT;
    }

    // The parent of source is 0
    p[source] = 0;

    // The distance from source to source is 0
    d[source] = 0;

    pq.push({d[source], source});

    while (!pq.empty()) {
      // Extract the node that has the minimum estimated cost from source
      auto entry = pq.top();
      pq.pop();

      int cost = entry.first;
      int node = entry.second;

      // If the current entry is not up to date
      if (cost > d[node]) {
        continue;
      }

      // For every neighbour, the cost from source is relaxed
      for (auto &edge : adj[node]) {
        int neighbour = edge.first;
        int cost_edge = edge.second;

        // If a lower cost is obtained by passing through node
        if (d[node] + cost_edge < d[neighbour]) {

          // Save the new cost
          d[neighbour] = d[node] + cost_edge;

          // The new parent for the neighbour is node
          p[neighbour] = node;

          // Update the cost of the node -> neighbour road
          pq.push({d[neighbour], neighbour});
        }
      }
    }

    for (int i = 1; i <= n; ++i) {
      if (d[i] == oo) {
        d[i] = 0;
      }
    }
  }

  // rebuild source -> ... -> node (if exists)
  vector<int> rebuild_path(int node, vector<int> &p) {
    // Cannot reach node from source
    if (p[node] == NO_PARENT) {
      return {};
    }

    // path = {source, ..., node}
    vector<int> path;

    // Rebuild node -> ... -> source (if exists)
    for (; node != 0; node = p[node]) {
      path.push_back(node);
    }

    // Resulted path node -> ... -> source
    // Revert the path
    reverse(path.begin(), path.end());

    return path;
  }

  void print_output() {
    ofstream fout("dijkstra.out");
    for (int i = 1; i <= n; ++i) {
      if (i == source) {
        continue;
      }
      cout << d[i] << " ";
    }
    fout.close();
   }
};

int main() {

  Task *task = new Task();
  task->solve();
  delete task;

  return 0;
}