#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits>


typedef std::pair<int, int> intPair;
typedef std::list<intPair> listOfPairs;
typedef std::vector<listOfPairs> vecOfLists;
typedef std::vector<intPair> vecOfPairs;
typedef std::priority_queue< int, vecOfPairs, std::greater<intPair> > pq;


std::vector<int> computeDists(vecOfLists &adj_list, int s_node)
{
    std::vector<int> dists(adj_list.size(), std::numeric_limits<int>::max());
    pq Q;

    dists[s_node] = 0;
    Q.emplace(dists[s_node], s_node);

    while (!Q.empty()) {
        intPair curr_entry = Q.top();
        Q.pop();

        if (curr_entry.first == dists[curr_entry.second]) {
            for (auto &i : adj_list[curr_entry.second]) {
                int cost = i.second;
                int vertex = i.first;

                if (curr_entry.first + cost < dists[vertex]) {
                    dists[vertex] = curr_entry.first + cost;
                    Q.emplace(dists[vertex], vertex);
                }
            }
        }
    }

    return dists;
}

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

    int N, M;
    fin >> N >> M;

    vecOfLists adj_list(N);
    for (int i = 0; i < M; ++i) {
        int x, y, cost;
        fin >> x >> y >> cost;
        --x, --y;

        adj_list[x].emplace_back(y, cost);
    }
    fin.close();

    std::vector<int> lenghts = computeDists(adj_list, 0);
    for (auto &i : lenghts)
        if (i == std::numeric_limits<int>::max())
            fout << 0 << " ";
        else
            fout << i << " ";

    fout.close();
    return 0;
}