#include <fstream>
#include <vector>
#include <climits>
#include <utility>
#include <set>
#include <tuple>

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

const int INF = INT_MAX;

struct compare {
    bool operator () (std::pair<int, int> & a, std::pair<int, int> & b) {
        return a.first < b.first;
    }
};

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

    std::set<std::pair<int, int>> tree;

    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;
    tree.insert ({0, 0});
    while (!tree.empty ()) {
        int intermediary, distance;
        std::tie (distance, intermediary) = *tree.begin ();
        tree.erase (tree.begin ());
//        int intermediary = heap.top ().second;
//        int distance = -heap.top ().first;
//        heap.pop ();

        for (auto & it : graph[intermediary])
            if (dist[it.first] > dist[intermediary] + it.second) {
                tree.erase ({dist[it.first], it.first});
                dist[it.first] = dist[intermediary] + it.second;
                tree.insert (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;
}