#include <fstream>
#include <queue>

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

int v[1001][1001], d[1001][1001], n, p, n_max;

int main() {
    p = 1;
    in >> n_max >> n;

    for (int a = 0; a < n; a++) {
        int i, j, c;
        in >> i >> j >> c;
        if (i > n_max) n_max = i;
        if (j > n_max) n_max = j;

        v[i][j] = c;
    }

    for (int i = 1; i <= n_max; i++)
        for (int j = 1; j <= n_max; j++) d[i][j] = 0x3f3f3f3f;

    d[p][p] = 0;

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>
        q;

    q.push(std::make_pair(0, p));

    while (!q.empty()) {
        std::pair<int, int> el = q.top();
        q.pop();

        for (int i = 1; i <= n_max; i++) {
            if (v[el.second][i] > 0 &&
                d[p][i] >= d[p][el.second] + v[el.second][i]) {
                d[p][i] = d[p][el.second] + v[el.second][i];
                q.push(std::make_pair(d[p][i], i));
            }
        }
    }

    for (int i = 2; i <= n_max; i++) {
        if (d[p][i] == 0x3f3f3f3f)
            out << 0 << ' ';
        else
            out << d[p][i] << ' ';
    }
}