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

struct nod {
    int x, c;

    bool operator<(const nod& o) const {
        return c > o.c;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<nod> g[n + 1];

    for (int i = 0, x, y, c; i < m; ++i) {
        cin >> x >> y >> c;
        g[x].push_back({y, c});
    }

    priority_queue<nod> pq;
    vector<int> d(n + 1, (int)1e18);
    pq.push({1, 0});
    d[1] = 0;

    while (!pq.empty()) {
        nod p = pq.top();
        pq.pop();
        
        if (p.c != d[p.x]) {
            continue;
        }

        for (nod q : g[p.x]) {
            if (d[q.x] > d[p.x] + q.c) {
                d[q.x] = d[p.x] + q.c;
                pq.push({q.x, d[q.x]});
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        cout << d[i] << " ";
    }
}