#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;
const int INF = 1e9;

vector<pair<int, int>> G[NMAX + 2]; // pair<nod, cost>
int N, M;

vector<int> dijkstra(int src)
{
    vector<int> best(N + 1, INF), viz(N + 1);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, src});
    best[src] = 0;
    while (!pq.empty()) {
        auto [cost_, nod_] = pq.top();
        pq.pop();
        int cost = cost_, nod = nod_;

        if (viz[nod])
            continue;
        viz[nod] = 1;

        for (auto [vecin, ed_cost] : G[nod]) {
            int new_cost = cost + ed_cost;
            if (new_cost < best[vecin]) {
                best[vecin] = new_cost;
                pq.push({new_cost, vecin});
            }
        }
        
    }

    for (int i = 2; i <= N; ++i) out << best[i] << " \n"[i == N];

    return best;
}


int main()
{
    in >> N >> M;
    for (int i = 1; i <= M; ++i) {
        int x,y, c;
        in >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

    dijkstra(1);
}