#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

//  Algoritmul lui Dijkstra

struct Nod {
    int val;
    int lg;

    Nod(int value, int length) {
        val = value;
        lg = length;
    }
    bool operator <(const Nod& n) const {
        return n.lg < lg;
    }
};

int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int n, m, x, y, lg;
    scanf("%d %d", &n, &m);
    vector<vector<Nod>> noduri(n + 1);

    while (m--) {
        scanf("%d %d %d", &x, &y, &lg);
        noduri[x].push_back(Nod(y, lg));
    }

    priority_queue<Nod> deParcurs;
    vector<int> minim(n + 1, -1);
    deParcurs.push(Nod(1, 0));
    minim[1] = 0;

    while (deParcurs.size()) {
        Nod from = deParcurs.top();
        deParcurs.pop();

        while (noduri[from.val].size()) {
            Nod to = noduri[from.val].back();
            if (to.lg + minim[from.val] < minim[to.val] || minim[to.val] < 0) {
                minim[to.val] = minim[from.val] + to.lg;
                deParcurs.push(Nod(to.val, to.lg + from.lg));
            }
            noduri[from.val].pop_back();
        }
    }
    for (x = 2; x <= n; x++)
        printf("%d ", max(minim[x], 0));
    return 0;
}