#include <bits/stdc++.h>
#define MAXN 50000
#define INF 0x3f3f3f

using namespace std;

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

struct vertex {
    int to, dist;
};

int main() {
    int n, m, d[MAXN];
    memset(d, INF, sizeof(int) * MAXN);
    fin >> n >> m;
    vector<vector<vertex>> graph(n, vector<vertex>());
    for (int i = 0; i < m; i++) {
        int from, to, dist;
        fin >> from >> to >> dist;
        from--, to--;
        graph[from].push_back({ to, dist });
    }

    set<pair<int, int>> next;
    next.insert({0, 0});
    while (!next.empty()) {
        pair<int, int> current = *next.begin();
        next.erase(next.begin());

        for (auto& v : graph[current.second]) {
            if (d[v.to] <= current.first + v.dist)
                continue;
            if (d[v.to] != INF)
                next.erase({ d[v.to], v.to });
            d[v.to] = current.first + v.dist;
            next.insert({ d[v.to], v.to });
        }
    }

    for (int i = 1; i < n; i++)
        fout << (d[i] == INT_MAX ? 0 : d[i]) << ' ';
    return 0;
}