#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int n, m;
    fin >> n >> m;

    vector<vector<pair<int, int>>> gr(n + 1);

    for (int i = 1; i <= m; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        gr[u].emplace_back(v, c);
    }

    set<pair<int, int>> s;
    vector<int> d(n + 1, 1e9);

    d[1] = 0;
    s.insert({0, 1});

    while (s.size() != 0) {
        int node, cost;

        tie(cost, node) = *s.begin();
        s.erase(s.begin());

        if (cost != d[node]) continue;

        for (auto &x : gr[node]) {
            if (cost + x.second < d[x.first]) {
                d[x.first] = cost + x.second;
                s.insert({d[x.first], x.first});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (d[i] == 1e9)
            d[i] = -1;

        fout << d[i] << ' ';
    }

    fout << '\n';
    return 0;
}