#include <bits/stdc++.h>
 
#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> dist;


    void read_input() {
        ifstream in("dijkstra.in");
        in >> n >> m;
        dist.resize(n + 1);

        source = 1;

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

        in.close();
    }
 
    void get_result() { 
        Dijkstra(source, dist); 
    }
 
    void Dijkstra(int source, vector<int> &dist) {
        for (int i = 1; i <= n; ++i) {
            dist[i] = oo;
        }

        dist[source] = 0;

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

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

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

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

                if (dist[node] + cost_edge < dist[neighbour]) {
                    dist[neighbour] = dist[node] + cost_edge;
                    pq.push({dist[neighbour], neighbour});
                }
            }
        }

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

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

        out.close();
    }
};
 
 
int main() {
    Task *task = new Task();
    task->solve();
    delete task;
    return 0;
}