#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f

using namespace std;

vector <vector <pair <int, int>>> v(50000);

vector <int> dijkstra(int s, int n) {
    vector <int> d(n + 1, inf);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair<int, int>>> Q;
    d[s] = 0;
    Q.push(make_pair(0, s));
    int nod, dest, cost;
    while (!Q.empty()) {
        auto curr = Q.top();
        nod = curr.second;
        Q.pop();

        if(d[nod] != curr.first)
            continue;

        for (auto muchie: v[nod]) {
            dest = muchie.first;
            cost = muchie.second;
            if (d[dest] > d[nod] + cost) {
                d[dest] = d[nod] + cost;
                Q.push(make_pair(d[dest], dest));
            }
        }

    }
    return d;
}

int main()
{
    int n, m, a, b, c;
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    vector <int> sol;
    sol = dijkstra(1, n);
    for (int i = 2; i <= n; i++)
        if (sol[i] == inf)
            out << "0 ";
        else
            out << sol[i] << " ";
    return 0;
}