#include <bits/stdc++.h>
#define ll long long
#pragma GCC optimize ("O3")
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
using namespace std;

const int INF = 1e9;

struct piii {
    int a, w;

    friend bool operator < (const piii &a, const piii &b) {
        return a.w > b.w;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ifstream cin ("dijkstra.in");
    ofstream cout ("dijkstra.out");

    int n, m; cin >> n >> m;
    vector <vector <pii>> adj(n + 2);
    vector <int> dist(n + 2, INF);

    for (int i = 1; i <= m; i ++) {
        int u, v, w; cin >> u >> v >> w;

        adj[u].pb({v, w});
    }

    dist[1] = 0;
    priority_queue<piii> q;
    q.push({1, 0});

    while (!q.empty()) {
        auto [node, costt] = q.top();
        q.pop();

        if (costt != dist[node]) continue;

        for (auto [to, w] : adj[node]) {
            if (dist[to] > costt + w) {
                dist[to] = costt + w;
                q.push({to, dist[to]});
            }
        }
    }

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

    return 0;
}