#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

vector<int> dijkstra(const int &source, const vector<vector<pair<int, int>>>& adj) {
    vector<int> dist(adj.size(), INF);
    vector<bool> visited(adj.size(), 0);
    priority_queue<pair<int, int>> pq;

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

    while (!pq.empty()) {
        int current = pq.top().second;
        pq.pop();

        visited[current] = 1;

        for (const auto& [neigh, cost] : adj[current])
            if (!visited[neigh] && dist[current] + cost < dist[neigh]) {
                dist[neigh] = dist[current] + cost;
                pq.push({-dist[neigh], neigh});
            }
    }

    return dist;
}

int main() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 1, x, y, c; i <= n; ++i) {
        fin >> x >> y >> c;
        adj[x].push_back({y, c});
    }

    vector<int> ans = dijkstra(1, adj);
    for (int i = 2; i <= n; ++i)
        fout << (ans[i] == INF ? 0 : ans[i]) << ' ';
    fout << '\n';
}