/// 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;
}