#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>

#define INF 0x3F3F3F3F
#define N 50000

using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue <pair <int, int>, greater <pair <int, int>>, pairing_heap_tag> myheap;

int dist[N+1];
vector <pair <int, int>> G[N+1];

int main () {
    ifstream fin ("dijkstra.in");
    ofstream fout ("dijkstra.out");

    int n, m;
    fin >> n >> m;

    int i, j, c;
    for (; m; m--) {
        fin >> i >> j >> c;
        G[i].push_back({c, j});
    }

    fill(&dist[2], &dist[n+1], INF);
    myheap PQ;
    PQ.push({0, 1});

    while (!PQ.empty()) {
        auto save=PQ.top();
        PQ.pop();

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

    for (i=2; i<=n; ++i)
        fout << (dist[i]==INF?0:dist[i]) << ' ';
    return 0;
}