#include <climits>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N, M;
vector<bool> visited;
vector<int> dist;
vector<vector<pair<int, int>>> G;

void dijkstra(int node) {
    dist[node] = 0;

    priority_queue<pair<int, int>> q;
    q.push({0, node});

    while (!q.empty()) {
        node = q.top().second;
        q.pop();
        if (visited[node])
            continue;
        visited[node] = true;

        for (auto edge : G[node]) {
            int neigh = edge.first;
            int cost = edge.second;
            if (dist[neigh] > dist[node] + cost) {
                dist[neigh] = dist[node] + cost;
                q.push({-dist[neigh], neigh});
            }
        }
    }
}

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

    scanf("%d %d", &N, &M);

    G.resize(N + 1);
    dist.resize(N + 1, INT_MAX);
    visited.resize(N + 1, false);

    for (int i = 1; i <= M; i++) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);

        G[x].push_back({y, c});
    }

    dijkstra(1);

    for (int i = 2; i <= N; i++) {
        printf("%d ", dist[i]);
    }

    return 0;
}