#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});
    }
}

bool cmp(const ll &a, const ll &b) {
    return d[a] < d[b];
}

void dijkstra() {
    set <ll, bool(*)(const ll &, const ll &)> s(&cmp);

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

    s.insert(1);

    while(!s.empty()) {
        ll node = *s.begin();
        s.erase(node);

        for(auto k : l[node]) {
            if(d[node] + k.second < d[k.first]) {
                if(d[k.first] != 1e9) {
                    s.erase(k.first);
                }
                d[k.first] = k.second + d[node];
                s.insert(k.first);
            }
        }
    }

    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;
}