#include <fstream>
#include <queue>

#define INF (1 << 30)

using namespace std;

void dijkstra(int src, vector<pair<int, int>> *adj, int n, ofstream &out) {

    vector<int> dist(n + 1, INF);
    dist[src] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int ,int>>> min_heap;
    min_heap.push({0, src});

    while (!min_heap.empty()) {

        int cost = min_heap.top().first;
        int node = min_heap.top().second;
        min_heap.pop();

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

        for (auto &neighbour : adj[node]) {
            if (dist[neighbour.first] > dist[node] + neighbour.second) {
                dist[neighbour.first] = dist[node] + neighbour.second;
                min_heap.push({dist[neighbour.first], neighbour.first});
            }
        }

    }

    for (int i = 1; i <= n; ++i) {
        if (i != src) {
            if (dist[i] == INF) {
                dist[i] = 0;
            }
            out << dist[i] << ' ';
        }
    }

}

int main() {

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

    int n, m;
    in >> n >> m;

    vector<pair<int, int>> adj[n + 1];

    int i;
    int u, v, weight;

    for (i = 0; i < m; ++i) {
        in >> u >> v >> weight;
        adj[u].push_back({v, weight});
    }

    dijkstra(1, adj, n, out);

    in.close();
    out.close();

    return 0;
}