#include <bits/stdc++.h>

#define int_pair std::pair <int, int>

#define MAXN     50005
#define INF 2000000005

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

inline void AddEdge(int X, int Y, int W) {
    ADC[X].push_back({Y, W});
}

std::priority_queue <int_pair, std::vector <int_pair>, std::greater <int_pair>> PQ;
int Dist[MAXN];
void Dijkstra(int Source = 1) {
    for (int i=1; i<=N; ++i)
        Dist[i] = INF;
    Dist[Source] = 0;

    PQ.push({0, Source});
    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[Edge.first] > Top.first + Edge.second)
                Dist[Edge.first] = Top.first + Edge.second,
                PQ.push({Dist[Edge.first], Edge.first});
    }
}

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

void Citire() {
    In >> N >> M;
    for (int i=1, X, Y, W; i<=M; ++i)
        In >> X >> Y >> W, AddEdge(X, Y, W);
}

void Rezolvare() {
    Dijkstra();
    for (int i=2; i<=N; ++i, Out << ' ')
        Out << (Dist[i] == INF ? 0 : Dist[i]);
}

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

    return 0;
}