#include <bits/stdc++.h>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N, M;
int D[50001];
int Visited[50001];
vector<pair<int, int>> G[50001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;

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

void Dijkstra() {
    for (int i = 2; i <= N; i++) D[i] = INT_MAX;
    PQ.push({0,1});

    while (!PQ.empty()) {
        pair<int, int> current = PQ.top();
        PQ.pop();

        Visited[current.second] = 1;
        for (auto next:G[current.second])
            if (!Visited[next.second] && D[next.second] > D[current.second] + next.first)
                D[next.second] = D[current.second] + next.first,
                        PQ.push(next);
    }

    for (int i = 2; i <= N; i++)
        if (D[i] == INT_MAX) g << "0 ";
        else g << D[i] << ' ';
}

int main() {
    Read();
    Dijkstra();
}