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

#define NMAX 50010
#define oo (1 << 30)

using namespace std;

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

  private:
    int n, m;
    int source;
    vector<pair<int, int>> adj[NMAX];
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                 std::greater<pair<int, int>>> pq;
    vector<int> d;
    vector<int> p;

    void read_input() {
        ifstream fin("dijkstra.in");

        fin >> n >> m;
        d.resize(n + 1);
        p.resize(n + 1);
        source = 1;

        for (int i = 1; i <= m; ++i) {
            int x, y, c;
            fin >> 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) {
            d[i] = oo;
            p[i] = -1;
        }

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

        while (!pq.empty()) {
            auto entry = pq.top();
            pq.pop();
            
            int cost = entry.first;
            int node = entry.second;

            if (cost > d[node]) {
                continue;
            }

            for (auto &edge : adj[node]) {
                int neighbor = edge.first;
                int cost_edge = edge.second;

                if (d[node] + cost_edge < d[neighbor]) {
                    d[neighbor] = d[node] + cost_edge;
                    p[neighbor] = node;
                    pq.push({d[neighbor], neighbor});
                }
            }
        }

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

    void print_output() {
        ofstream fout("dijkstra.out");
        for (int i = 2; i < d.size(); ++i) {
            fout << d[i] << " ";
        }
        fout << "\n";
        fout.close();
    }
};

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

    return 0;
}