#include <fstream>
#include <vector>
#include <climits>
#include <utility>
#include <queue>

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

const int INF = INT_MAX;

int main () {
    int n, m; fin >> n >> m;
    std::vector<int> dist(n, INF);

    std::priority_queue<std::pair<int, int>> heap;

    std::vector<std::vector<std::pair<int, int>>> graph(
            n, std::vector<std::pair<int, int>> ());

    while (m > 0) {
        int u, v, c; fin >> u >> v >> c; u -= 1, v -= 1;
        graph[u].emplace_back (std::make_pair (v, c));
        m -= 1;
    }


    dist[0] = 0;
    heap.push (std::make_pair (0, 0));
    while (!heap.empty ()) {
        int intermediary = heap.top ().second;
        int distance = -heap.top ().first;
        heap.pop ();

        if (dist[intermediary] < distance)
            continue;

        for (auto & it : graph[intermediary])
            if (dist[it.first] > dist[intermediary] + it.second) {
                dist[it.first] = dist[intermediary] + it.second;
                heap.push (std::make_pair (-dist[it.first], it.first));
            }
    }

    for (int i = 1; i < (int) dist.size (); i += 1)
        fout << (dist[i] != INF ? dist[i] : 0) << ' ';
    return 0;
}