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

const int inf = 2000000000;
using namespace std;

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

int main() {

    int n, m, x, y, cost;
    fin >> n >> m;

    priority_queue<pair<int, int>> PQ;
    vector<vector<pair<int,int>>> L(n + 1);

    vector<int> d(L.size(), inf), viz(n + 1, 0);
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> cost;
        L[x].push_back({y,cost});
    }

    d[1]=0;
    PQ.push({-d[1], 1});
    while (!PQ.empty()) {
        int nod = PQ.top().second;
        PQ.pop();
        if (viz[nod]) {
            continue;
        }
        viz[nod] = 1;
        for (auto x : L[nod]) {
            int vecin = x.first;
            int cost = x.second;
            if (d[vecin] > d[nod] + cost) {
                d[vecin] = d[nod] + cost;
                PQ.push({-d[vecin], vecin});
            }
        }
    }
    for (int i = 2; i<= n; i++) {
        if (d[i] == inf) 
            fout << "0 ";
        else 
            fout << d[i] << " ";
    }
    return 0;
}