// https://infoarena.ro/job_detail/2611521?action=view-source

#include <bits/stdc++.h>

#define FILE_I "dijkstra.in"
#define FILE_O "dijkstra.out"
#define INF (1 << 30)
#define p pair<int, int>
#define NMAX 50100

using namespace std;

class Task {
  int n, m;
  std::vector<p> adj[NMAX];
  vector<int> distante;

 public:
  void solve() {
    read();
    fa();
    print();
  }

 private:
  void read() {
    std::ifstream fin(FILE_I);
    fin >> n >> m;
    distante = vector<int>(n + 1, INF);

    int x, y, z;
    for (int i = 0; i < m; ++i) {
      fin >> x >> y >> z;
      // cout << x << " " << y << " " << z << "\n";
      adj[x].push_back({z, y});
      // cout << adj[x][0].first << " " << adj[x][y].second << "\n";
    }
    
    fin.close();
  }

  void fa() {
    priority_queue< pair<int, int>> q;
    q.push({0, 1}); // bagam nodul 1
    distante[1] = 0;
    // cout << "size: " << q.size() << "\n";

    while (q.empty() == false) {
      int nod = q.top().second;
      q.pop();
      // cout << "node: " << nod << "\n";
      for (auto &elem : adj[nod]) {
        int cost = elem.first;
        int next_node = elem.second;
        // cout << "(" << next_node << ", " << cost << ") ";
        if (distante[nod] + cost < distante[next_node]) {
          distante[next_node] = distante[nod] + cost;
          q.push({distante[next_node], next_node});
        }
        // cout << "\n";
      }
    }
  }



  void print() {
    std::ofstream fout (FILE_O);
    for (unsigned int i = 2; i < distante.size(); ++i) {
      fout << distante[i] << " ";
    }
    fout.close();
  }
};

int main() {
  Task *t = new Task();
  t->solve();
  delete t;
  return 0;
}