#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;
typedef unsigned long long ull;

const ll nmx = 5e4 + 5;

ll N, M, d[nmx];
vector <pair<ll,ll>> l[nmx];

void read() {
    in>>N>>M;

    for(int i = 1; i <= M; ++i) {
        ll A, B, C;
        in>>A>>B>>C;
        l[A].push_back({B, C});
    }
}

void dijkstra() {
    set <pair<ll,ll>> s;

    for(int i = 2; i <= N; ++i) {
        d[i] = 1e9;
    }

    s.insert({0, 1});

    while(!s.empty()) {
        ll node = s.begin()->second;
        ll dist = s.begin()->first;
        s.erase(s.begin());

        for(auto k : l[node]) {
            ll to = k.first;
            ll cost = k.second;
            if(d[to] > d[node] + cost) {
                if(d[to] != 1e9) {
                    s.erase(s.find({d[to], to}));
                }
                d[to] = d[node] + cost;
                s.insert({d[to], to});
            }

        }
    }

    for(int i = 2; i <= N; ++i) {
        if(d[i] == 1e9) {
            d[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);

    read();
    dijkstra();

    for(int i = 2; i <= N; ++i) out<<d[i]<<" ";

    return 0;
}