// https://www.infoarena.ro/problema/dijkstra

// dijkstra clasic cu heap O(m log n)
// pentru graf dens (m ~ n^2) e mai rapid varianta cu array O(n^2), dar nu o pun aici

#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#define MAXN 50001

using namespace std;

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

struct edge {
    int to, w;
};

vector<edge> g[MAXN];
long long d[MAXN];

int main() {
    int n, m;
    fin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, w;
        fin >> a >> b >> w;
        g[a].push_back({b, w}); // graf orientat
    }

    for (int i = 1; i <= n; i++)
        d[i] = LLONG_MAX;
    d[1] = 0;

    // (dist, nod), min-heap pe dist
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (du > d[u]) // intrare invechita
            continue;
        for (auto &e : g[u]) {
            long long nd = du + e.w;
            if (nd < d[e.to]) {
                d[e.to] = nd;
                pq.push({nd, e.to});
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        fout << (d[i] == LLONG_MAX ? 0 : d[i]);
        fout << " \n"[i == n];
    }
    return 0;
}