#include <bits/stdc++.h>

#define llg long long
#define inf (int)(1e9)

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

int N, M;
std::vector <std::vector <std::pair <int, int>>> ADC;
std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int>>, std::greater <std::pair <int, int>>> PQ;

std::vector <int> Dijkstra(int Start) {
    std::vector <int> Dist(N, inf);
    Dist[Start] = 0;

    PQ.push({0, Start});

    int TopNode, TopDist;
    while (!PQ.empty()) {
        TopDist = PQ.top().first;
        TopNode = PQ.top().second;
        PQ.pop();

        if (TopDist != Dist[TopNode]) continue;

        for (auto Edge:ADC[TopNode]) {
            if (Edge.first + Dist[TopNode] < Dist[Edge.second])
                Dist[Edge.second] = Dist[TopNode] + Edge.first;
                PQ.push({Dist[Edge.second], Edge.second});
        }
    }   return Dist;
}

void Citire() {
    In >> N >> M;
    ADC.resize(N);

    for (int i=0, x, y, c; i<M; ++i)
        In >> x >> y >> c,
        ADC[x-1].push_back(std::make_pair(c, y-1));
}

void Rezolvare() {
    std::vector <int> Ans = Dijkstra(0);
    for (int i=1; i<N; ++i)
        if (Ans[i] == inf) Out << "-1\n";
        else Out << Ans[i] << ' ';
}

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

    return 0;
}