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

using namespace std;

struct Nod {
    int n;
    int dist;

    friend bool operator<(const Nod& lhs, const Nod& rhs) {
        return lhs.dist > rhs.dist;
    }
};

struct Muchie {
    int nod;
    int cost;
};

int main() {
    ifstream in("dijkstra.in");

    int n, m;
    in >> n >> m;

    vector<vector<Muchie>> graf(n);

    for (int i = 0; i < m; ++i) {
        int start, dest, cost;
        in >> start >> dest >> cost;
        graf[start - 1].push_back(Muchie { dest - 1, cost });
    }

    vector<int> distances(n, INT_MAX);
    vector<bool> visited(n);

    priority_queue<Nod> coada;
    coada.push(Nod { 0, 0 });

    while (!coada.empty()) {
        Nod curr = coada.top();
        coada.pop();

        if (curr.dist > distances[curr.n]) {
            continue;
        }

        for (Muchie m : graf[curr.n]) {
            if (visited[m.nod]) {
                continue;
            }

            int newDist = curr.dist + m.cost;

            if (newDist < distances[m.nod]) {
                distances[m.nod] = newDist;
                coada.push(Nod { m.nod, distances[m.nod] });
            }
        }

        visited[curr.n] = true;
    }

    ofstream out("dijkstra.out");
    for (int i = 1; i < n; ++i) {
        if (!visited[i]) {
            out << 0 << ' ';
        } else {
            out << distances[i] << ' ';
        }
    }
    out << '\n';
}