#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 50001;
const int INF = (1LL << 31) - 1;

int N, M;
vector < pair < int, int > > G[NMAX];

vector < int > dijkstra(int source) {

    vector < int > distance(N + 1, INF);
    priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > pq;

    pq.push({ 0, source });
    distance[source] = 0;

    for(;!pq.empty();) {

        int cost = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(distance[node] != cost)
            continue;

        for(auto& neighbor : G[node]) {
            if(distance[neighbor.first] > distance[node] + neighbor.second) {
                distance[neighbor.first] = distance[node] + neighbor.second;
                pq.push({ distance[neighbor.first], neighbor.first });
            }
        }
    }

    return distance;
}

int main() {

    f >> N >> M;

    for(;M--;) {

        int x, y, c;
        f >> x >> y >> c;

        G[x].push_back({ y, c });
    }

    auto sol = dijkstra(1);

    for(int i = 2;i <= N;++i)
        g << (sol.at(i) == INF ? 0 : sol.at(i)) << ' ';

    return 0;
}