#include <bits/stdc++.h>
#define MAXN 50005
#define INF 2000000005
using namespace std;

int N, M;

vector <pair <int, int>> ADC[MAXN];

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

}



 priority_queue <pair <int, int>,  vector <pair <int, int>>,  greater <pair <int, int>>> 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});

    pair <int, int> 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});

    }

}

 ifstream In ("dijkstra.in");
 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;

}