#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <list>
#include <stack>
using namespace std;

const int inf = 100000;

int main() {
    ifstream f("dijkstra.in");
    int m, n;
    f >> n >> m;
    vector<list<pair<int, int>>> muchii(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        f >> a >> b >> w;
        muchii[a].push_back(make_pair(b, w));
    }
    vector<int> dist(n + 1);

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> queue;
    for (int i = 2; i <= n; i++) {
        dist[i] = inf;
    }
    dist[1] = 0;
    queue.push(make_pair(0, 1));

    while (!queue.empty()) {
        int node = queue.top().second;
        queue.pop();

        for (auto& i : muchii[node]) {
            int d = dist[node] + i.second;
            if (d < dist[i.first]) {
                dist[i.first] = d;
                queue.push(make_pair(dist[i.first], i.first));
            }
        }
    }

    ofstream g("dijkstra.out");
    for (int i = 2; i <= n; i++) {
        g << (dist[i] == inf ? 0 : dist[i]) << " ";
    }

    return 0;
}