#include <bits/stdc++.h>
#include <limits>
using namespace std;

const long long INF = 1e18;
const int NMAX = 50'001;

vector<pair<int, int>> adj[NMAX];
long long dist[NMAX];

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

int n, m;

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[s] = 0;

    pq.push({0, s});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int cost = edge.second;

            if (dist[u] + cost < dist[v]) {
                dist[v] = dist[u] + cost;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({v, c});
    }

    dijkstra(1);

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