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

const long long INF = 1LL << 60;

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> q;

vector<int> s[50005];
vector<long long> cc[50005];
long long l[50005];

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");

    int n, m, x, y;
    long long c;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> c;
        s[x].push_back(y);
        cc[x].push_back(c);
    }

    for (int i = 1; i <= n; ++i) {
        l[i] = INF;
    }
    l[1] = 0;
    q.emplace(0, 1);

    while (!q.empty()) {
        long long ct = q.top().first;
        int in = q.top().second;
        q.pop();

        if (ct > l[in]) continue;

        for (size_t i = 0; i < s[in].size(); ++i) {
            int vecin = s[in][i];
            long long cost = cc[in][i];
            if (ct + cost < l[vecin]) {
                l[vecin] = ct + cost;
                q.emplace(l[vecin], vecin);
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        cout << (l[i] == INF ? 0 : l[i]) << " ";
    }

    return 0;
}