/// DIJKSTRA
#include<fstream>
#include<vector>
#include<queue>
#include<limits>

using namespace std;

typedef numeric_limits<short> SLIM;
typedef numeric_limits<unsigned> ULIM;
typedef pair<unsigned, int> NODE;

class Graph {

private:
    vector<vector<short> > adjList;
    int numNodes, numArcs;
public:
    Graph(const char(&)[12]);
    vector<unsigned> distanceFrom0;
    void dijkstra();

    void printDistances(const char(&outFileName)[13]) {
        ofstream outStr(outFileName);
        for(int i = 1; i < numNodes; i++)
            if(distanceFrom0[i] == ULIM::max())
                outStr << 0 << ' ';
            else
                outStr << distanceFrom0[i] << ' ';
    };

};

Graph::Graph(const char (&inFileName)[12]) {
    ifstream inStr(inFileName);

    inStr >> numNodes >> numArcs;
    adjList.assign(numNodes, vector<short>(numNodes, SLIM::max()));
    int from, to;
    for(int i = 0; i < numNodes; i++) {
        inStr >> from >> to;
        inStr >> adjList[from-1][to-1];
    }
}

void Graph::dijkstra() {
    priority_queue<NODE, vector<NODE>, greater<NODE> > nodes;
    distanceFrom0.assign(numNodes, ULIM::max());
    distanceFrom0[0] = 0;
    int current = 0;
    unsigned alt;
    nodes.push(NODE(distanceFrom0[current], current));

    while(!nodes.empty()) {
        current = nodes.top().second;
        if(nodes.top().first != distanceFrom0[current]) {
            nodes.pop();
            nodes.push(NODE(distanceFrom0[current], current));
        }
        nodes.pop();

        for(int i = 0; i < numNodes; i++)
            if(adjList[current][i] != SLIM::max()) {
                alt = distanceFrom0[current] + adjList[current][i];
                if(alt < distanceFrom0[i]) {
                    distanceFrom0[i] = alt;
                    nodes.push(NODE(distanceFrom0[i], i));
                }
            }
    }
}

int main() {
    const char inFileName[12] = "dijkstra.in";
    const char outFileName[13] = "dijkstra.out";

    Graph graph(inFileName);
    graph.dijkstra();
    graph.printDistances(outFileName);

    return 0;
}