#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

const ll INF = 1e18;

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    vector <vector <pair <int, int>>> g(n + 1);
    for(i = 1; i <= m; i++) {
        int x, y, z; cin >> x >> y >> z;
        g[x].push_back({y, z});
    }

    vector <ll> dst(n + 1, INF);
    vector <bool> vis(n + 1);

    priority_queue <pair <ll, int>> pq;
    pq.push({0, 1}), dst[1] = 0;

    while(pq.size()) {
        auto cur = pq.top();
        pq.pop(), cur.first *= -1;
        if(vis[cur.second]) continue;

        dst[cur.second] = cur.first;
        vis[cur.second] = 1;
        for(auto it : g[cur.second]) {
            if(dst[it.first] > cur.first + it.second) {
                dst[it.first] = cur.first + it.second;
                pq.push({-dst[it.first], it.first});
            }
        }
    }

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

    return 0;
}