/// 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;
typedef vector<NODE>::iterator VNIT;

class Graph {

private:
    vector<vector<NODE> > adjList;
    vector<unsigned> distanceFrom0;
    int numNodes, numArcs;
public:
    Graph(ifstream &);
    void dijkstra();

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

};

Graph::Graph(ifstream &inStr) {
    inStr >> numNodes >> numArcs;
    adjList.resize(numNodes);
    int from, to;
    int cost;
    for(int i = 0; i < numArcs; i++) {
        inStr >> from >> to;
        inStr >> cost;
        adjList[from-1].push_back(NODE(cost, to-1));
    }
}

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

    nodes.push(NODE(distanceFrom0[current], current));

    while(!nodes.empty()) {
        if(nodes.top().first != distanceFrom0[nodes.top().second])
            nodes.pop();

        current = nodes.top().second;
        nodes.pop();

        for(VNIT it = adjList[current].begin(); it != adjList[current].end(); it++) {
            currNeigh = it->second;
            distCurrNeigh = it->first;

            alt = distanceFrom0[current] + distCurrNeigh;

            if(alt < distanceFrom0[currNeigh]) {
                distanceFrom0[currNeigh] = alt;
                nodes.push(NODE(distanceFrom0[currNeigh], currNeigh));
            }
        }
    }
}

int main() {
    ifstream inStr("dijkstra.in");
    ofstream outStr("dijkstra.out");

    Graph graph(inStr);
    graph.dijkstra();
    graph.printDistances(outStr);

    return 0;
}