#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int nmax = 5e4 + 10;

int n, m;
vector < pair < int, int > > g[nmax];

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);

        g[x].push_back({y, z});
    }
}

void run_dijkstra() {
    int D[nmax];
    priority_queue < pair < int, int > > pq;
    for (int i = 1; i <= n; ++i) D[i] = inf;

    D[1] = 0; pq.push({-D[1], 1});
    while (pq.size()) {
        int node, cost; tie(cost, node) = pq.top(); pq.pop();
        if (D[node] != -cost) continue;

        for (auto &it : g[node]) {
            if (D[node] + it.second >= D[it.first]) continue;

            D[it.first] = D[node] + it.second;
            pq.push({-D[it.first], it.first});
        }
    }

    ///output
    for (int i = 2; i <= n; ++i)
        (D[i] == inf) ? printf("0 ") : printf("%d ", D[i]);
}

int main() {
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    input();
    run_dijkstra();

    return 0;
}