#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 > dist(N + 1, INF);
    priority_queue< pair < int, int >, vector < pair < int, int > >, greater <> > pq;

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

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

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

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

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

    return dist;
}

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;
}