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

const int INF = INT_MAX;

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

struct Muchie {
    int nod, w;
    friend bool operator < (const Muchie& a, const Muchie& b) {
        return a.w > b.w;
    }
};

void dijkstra(vector<vector<Muchie>>& adj, array<int, 50001>& dist, int N) {
    priority_queue<Muchie> pq;
    dist[1] = 0;
    pq.push({1, 0});
    while (!pq.empty()) {
        const Muchie k = pq.top();
        pq.pop();
        int u = k.nod;
        int dist_u = k.w;
        if (dist_u > dist[u]) continue;
        for (const auto& t : adj[u]) {
            int v = t.nod;
            int w = t.w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.push({v, dist[v]});
            }
        }
    }
    for (int i = 2; i <= N; i++) {
        if (dist[i] == INF)
            out << "0 ";
        else
            out << dist[i] << " ";
    }
}

int main() {
    int N, M;
    in >> N >> M;

    vector<vector<Muchie>> adj(N + 1);
    array<int, 50001> dist;
    dist.fill(INF);

    for (int i = 0; i < M; i++) {
        int a, b, c;
        in >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    dijkstra(adj, dist, N);
    return 0;
}