#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;

struct Min {
    int nod, cost;
};

struct compare {
    bool operator () (Min & a, Min & b) {
        return a.cost < b.cost;
    }
};

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

    std::priority_queue<Min, std::vector<Min>, compare> heap;

    std::vector<std::vector<Min>> graph(n, std::vector<Min> ());

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


    dist[0] = 0;
    heap.push (Min {0, 0});
    while (!heap.empty ()) {
        int intermediary = heap.top().nod;
        int distance = heap.top ().cost;
        heap.pop ();

        if (dist[intermediary] < distance)
            continue;

        for (Min & it : graph[intermediary])
            if (dist[it.nod] > dist[intermediary] + it.cost) {
                dist[it.nod] = dist[intermediary] + it.cost;
                heap.push (Min {it.nod, dist[it.nod]});
            }
    }

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