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

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

const int nMax = 5e4;
const int INF = INT_MAX;

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

std::bitset<nMax> vis;

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

    std::priority_queue<std::pair<int, int>,
        std::vector<std::pair<int, int>>, compare> 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 (vis[intermediary] == 0) {
            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));
            }
            vis[intermediary] = 1;
        }
    }

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