#include <bits/stdc++.h>
#define maxn 50001

using namespace std;

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

int n, m, a, b, c, distanta[maxn];
vector <pair <int, int> > graf[maxn];
bitset <maxn> valid;
priority_queue <pair <int, int> > coada;

void citire() {
    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> a >> b >> c;
        graf[a].push_back({b, c});
    }
}

int main() {
    citire();

    memset(distanta, 127, sizeof(distanta));
    distanta[1] = 0;

    for (int i = 1; i <= n; ++i) {
        coada.push({-distanta[i], i});
        valid[i] = 1;
    }

    while (!coada.empty()) {
        pair <int, int> aux = coada.top();
        coada.pop();

        if (distanta[aux.second] != -aux.first)
            continue;

        int pozitie = aux.second;
        valid[pozitie] = 0;

        for (auto it:graf[pozitie])
            if (valid[it.first] && distanta[it.first] > distanta[pozitie] + it.second) {
                    distanta[it.first] = distanta[pozitie] + it.second;
                    coada.push({-distanta[it.first], it.first});
            }
    }

    for (int i = 2; i <= n; ++i)
        if (distanta[i] == 2139062143)
            out << "0";
        else
            out << distanta[i] << " ";
    return 0;
}