#include <bits/stdc++.h>

using namespace std;

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

struct Elem {
    int nod;
    int d;

    bool operator<(const Elem& other) const {
        return d < other.d;
    }
};

int n, m, x, y, z;
vector<pair<int, int>> g[50001];
vector<int> dist(50001, -1);
priority_queue<Elem> q;
bool viz[50001];

void dij() {
    q.push({ 1, 0 });
    dist[1] = 0;

    while (!q.empty()) {
        auto t = q.top().nod;
        q.pop();

        if (!viz[t]) {
            viz[t] = 1;

            for (auto& x : g[t]) {
                if (dist[x.first] == -1 || dist[x.first] > dist[t] + x.second) {
                    dist[x.first] = dist[t] + x.second;
                    q.push({ x.first, dist[x.first] });
                }
            }
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> z;
        g[x].push_back(make_pair(y, z));
    }
    dij();
    for (int i = 2; i <= n; i++) {
        fout << max(dist[i], 0) << " ";
    }
}