#include <bits/stdc++.h>
using namespace std;

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

signed main() {
    int n, m;
    fin >> n >> m;
    vector<pair<int, int>> graph[n + 1];
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        graph[x].push_back({y, z});
    }
    const int s = 1;
    vector<int> d(n + 1, INT_MAX);
    set<pair<int, int>> distSet;
    distSet.insert({0, s});
    d[s] = 0;
    while (!distSet.empty()) {
        pair<int, int> current = *(distSet.begin());
        distSet.erase(distSet.begin());
        int currentNode = current.second;
        for (auto nodePair : graph[currentNode]) {
            int node = nodePair.first;
            int cost = nodePair.second;
            if (d[node] > d[currentNode] + cost) {
                if (d[node] != INT_MAX) {
                    distSet.erase(distSet.find({d[node], node}));
                }
                d[node] = d[currentNode] + cost;
                distSet.insert({d[node], node});
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (d[i] == INT_MAX) {
            fout << "0 ";
        } else {
            fout << d[i] << " ";
        }
    }
    return 0;
}