#include <bits/stdc++.h>

#define MAXN 50005
#define inf  (int)(1e9)
#define int_pair std::pair <int, int>

int N, M;
std::vector <int_pair> ADC[MAXN];

inline void AddEdge(int x, int y, int w) {
    ADC[x].push_back({y, w});
}

#define Vecin Edge.first

int Dist[MAXN];
std::priority_queue <int_pair, std::vector <int_pair>, std::greater <int_pair>> PQ;

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

    int_pair Top;
    while (!PQ.empty()) {
        Top = PQ.top();
        PQ.pop();

        if (Top.first != Dist[Top.second]) continue;
        for (auto Edge:ADC[Top.second])
            if (Dist[Vecin] > Dist[Top.second] + Edge.second)
                Dist[Vecin] = Dist[Top.second] + Edge.second,
                PQ.push({Dist[Vecin], Vecin});
    }
}

std::ifstream In("dijkstra.in");
std::ofstream Out("dijkstra.out");

void Citire() {
    In >> N >> M;
    for (int i=0, x, y, w; i<M; ++i)
        In >> x >> y >> w, AddEdge(x, y, w);
}

void Rezolvare() {
    Dijkstra();
    for (int i=2; i<=N; ++i)
        if (Dist[i] == inf) Out << 0 << ' ' ;
        else Out << Dist[i] << ' ' ;
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}