#include <fstream>

#include <vector>

#include <queue>

using namespace std;

ifstream fin ("dijkstra.in");

ofstream fout ("dijkstra.out");

int main () {

    int n, m;

    fin >> n >> m;

    vector<vector<pair<int, int>>> graph (n + 1);

    for (int i = 1; i <= m; ++i) {

        int a, b, c;

        fin >> a >> b >> c;

        graph[a].push_back({b, c});
    }

    const long long INF = 1LL << 60;

    vector<long long> dist (n + 1, INF);

    dist[1] = 0;

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

    pq.push({0, 1});

    while (!pq.empty()) {

        auto minim = pq.top();

        pq.pop();

        int d = minim.first, nod = minim.second;

        if (d > dist[nod])
            continue;

        for (auto vecin : graph[nod]) {

            int new_dist = dist[nod] + vecin.second;

            if (new_dist < dist[vecin.first]) {

                dist[vecin.first] = new_dist;

                pq.push({dist[vecin.first], vecin.first});
            }
        }
    }

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

    return 0;
}