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

struct Edge {
    int v, w;
    bool operator< (const Edge &other) const {
        return w > other.w;
    }
};

const int INF = 2e9;

vector<vector<Edge>> adj;
vector<int> dist;

void dijkstra(int s) {
    priority_queue<Edge> pq;
    dist[s] = 0;
    pq.push({s, 0});

    while (!pq.empty()) {
        auto c_edge = pq.top(); pq.pop();
        int u = c_edge.v, c_dist = c_edge.w;

        if (c_dist > dist[u]) continue;

        for (auto edge : adj[u]) {
            int v = edge.v, w = edge.w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }
}

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

    int n, m;
    cin >> n >> m;

    adj.assign(n + 1, vector<Edge>());
    dist.assign(n + 1, INF);

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    dijkstra(1);

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

    return 0;
}