#include <iostream>
#include <queue>

#define MAXN 50000

using namespace std;

int dist[MAXN + 1];
vector<vector<pair<int, int>>> edges;
priority_queue<pair<int, int>> pq;

void dijkstra(int src) {
    pq.push({0, src});
    dist[src] = 0;

    while (!pq.empty()) {
        auto[currdist, node] = pq.top();
        pq.pop();
        currdist = -currdist;

        if (currdist == dist[node]) {
            for (auto[nxt, cost]: edges[node]) {
                if (dist[nxt] == -1 || dist[nxt] > dist[node] + cost) {
                    dist[nxt] = dist[node] + cost;
                    pq.push({-dist[nxt], nxt});
                }
            }
        }
    }
}

int main() {
    FILE *fin, *fout;
    int n, m, a, b, c, i;

    fin = fopen("dijkstra.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    edges.resize(n + 1);
    for (i = 1; i <= m; i++) {
        fscanf(fin, "%d%d%d", &a, &b, &c);
        edges[a].push_back({b, c});
    }
    fclose(fin);

    for (i = 1; i <= n; i++) {
        dist[i] = -1;
    }

    dijkstra(1);

    fout = fopen("dijkstra.out", "w");
    for (i = 2; i <= n; i++) {
        fprintf(fout, "%d ", (dist[i] == -1) ? 0 : dist[i]);
    }
    fclose(fout);

    return 0;
}