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

using namespace std;

typedef numeric_limits<short> SLIMITS;
typedef numeric_limits<int> ILIMITS;
typedef pair<int, int> NODE;

void printLong(vector<int> &values, const char outFileName[]) {
    ofstream outStr(outFileName);
    const int MAX = ILIMITS::max();

    for(int i = 1; i<values.size(); i++)
        if(values[i] != MAX)
            outStr << values[i] << ' ';
}

class Graph {

private:
    vector< vector<short> > adjList;
    int numNodes, numArcs;
public:
    Graph(const char[]);
    vector<int> dijkstra(int);
    int getNumNodes() {return numNodes;}

};

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

    inStr >> numNodes >> numArcs;
    adjList.assign(numNodes, vector<short>(numNodes, SLIMITS::max()));
    int from, to;
    for(int i = 0; i < numArcs; i++) {
        inStr >> from >> to ;
        inStr >> adjList[from-1][to-1];
    }
}
/**priority gueue uses the great class
 so it will work with the SMALLEST value instead of the greatest
 contains pairs, will be sorted by the first value */

vector<int> Graph::dijkstra(int source) {
    priority_queue<NODE, vector<NODE>, greater<NODE> > setOfAllNodes;
    vector<int> distances(numNodes, ILIMITS::max());
    distances[source] = 0;
    setOfAllNodes.push(NODE(distances[source], source));

    int current;
    long alt;
    while(!setOfAllNodes.empty()) {
        current = setOfAllNodes.top().second;  /// .second: a sorszam
        if(distances[current] != setOfAllNodes.top().first) {  /// REFRESHING
            setOfAllNodes.pop();
            setOfAllNodes.push(NODE(distances[current], current));
        }
        else {
            setOfAllNodes.pop();
            for(int i = 0; i < numNodes; i++)
                if(adjList[current][i] < SLIMITS::max()) {  ///IF IT IS A NEIGHBOUR
                    alt = distances[current] + adjList[current][i];
                    if(alt < distances[i]) {        /// IF THERE IS A BETTER WAY TO IT
                        distances[i] = alt;
                        setOfAllNodes.push(NODE(distances[i], i));
                    }
                }
        }
    }

    return distances;
}

int main() {
    const char inFileName[] = "dijkstra.in";
    const char outFileName[] = "dijkstra.out";
    Graph graph(inFileName);
    vector<int> dist = graph.dijkstra(0);

    printLong(dist, outFileName);

    return 0;
}