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

const int INF = INT32_MAX - 1;

struct Edge
{
    int from, to;
    int cost;
};

//std::list<Edge> adjacencyList;
//std::vector<std::list<Edge>::iterator> fromIndexes;


int main()
{
    std::ifstream fin("dijkstra.in");
    int nNodes, nEdges;
    std::vector<std::vector<Edge>> edges;

    fin >> nNodes >> nEdges;
    edges.insert(edges.begin(), static_cast<unsigned long>(nNodes), {});
    for(int i = 0; i < nEdges; i++)
    {
        Edge e{};
        fin >> e.from >> e.to >> e.cost;

        e.from --;
        e.to --;
        edges[e.from].push_back(e);
    }
/*    fromIndexes.insert(fromIndexes.begin(), static_cast<unsigned long>(nNodes), {});
    for(int i = 0; i < nEdges; i++)
    {
        Edge e{};
        fin >> e.from >> e.to >> e.cost;

        if(fromIndexes[e.from] == std::list<Edge>::iterator{})
        {
            adjacencyList.push_front(e);
            fromIndexes[e.from] = adjacencyList.begin();

            std::cout << "new from index: " << e.from << " -> "<< e.to << std::endl;
        }
        else
        {
            auto cp = fromIndexes[e.from];
            cp++;
            adjacencyList.insert(cp, 0, e);
            std::cout << "old: " << e.from << " -> "<< e.to << std::endl;
        }
    }

    for(auto it = fromIndexes[4]; it != adjacencyList.end() && it->from == 4; it++)
    {
        std::cout << it->to << std::endl;
    }*/

    std::vector<int> distances;
    std::vector<bool> was;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    distances.insert(distances.begin(), static_cast<unsigned long>(nNodes), INF);
    was.insert(was.begin(), static_cast<unsigned long>(nNodes), false);

    distances[0] = 0;
    pq.push({distances[0], 0});
    while(!pq.empty())
    {
        while(!pq.empty() && was[pq.top().second])
            pq.pop();

        if(!pq.empty())
        {
            int x = pq.top().second;
            pq.pop();

            for(auto edge: edges[x])
            {
                if(distances[x] + edge.cost < distances[edge.to])
                {
                    distances[edge.to] = distances[x] + edge.cost;
                    pq.push({distances[edge.to], edge.to});
                }
            }
        }
    }

    std::ofstream fout("dijkstra.out");
    for(int i = 1; i < nNodes; i++)
        if(distances[i] != INF)
            fout << distances[i] << ' ';
        else fout << 0 << ' ';

    return 0;
}