#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

class Graph {
    //private attributes
    vector<vector<int>> edges;
    vector<vector<pair<int, int>>> edgesCost;
    int numberOfNodes;

    //-------------------------------------

    //private methods
    void DFS(unordered_map<int, bool>&, int);
    void tarjan(int, int&, vector<int>&, vector<int>&, stack<int>&,
            unordered_map<int ,bool>&, unordered_map<int ,bool>&, vector<vector<int>>&);
//    void bicomponentsDFS(int, int, unordered_map<int, bool>, stack<int>,
//            vector<int>, vector<int>, int&, vector<vector<int>>& );
    void topologicalSortingDFS(int,  vector<bool>&, stack<int>&);
public:
    Graph(int);
    ~Graph();
    void setEdge(int, int);
    void displayEdges();
    void topologicalSort();
    vector<int> distance(int);
    vector<vector<int>> SCC();
    int numberOfComponents();
//    void biconnectedComponents();
    bool havelHakimi(vector<int>);
    void setEdgeCost(int , int , int );
    vector<int> Dijkstra(int, int);
};

void resolveSSC(){
    int numberOfNodes, numberOfEdges, from, to;

    cin >> numberOfNodes >> numberOfEdges;

    auto* graph = new Graph(numberOfNodes);

    for (int countEdge = 1; countEdge <= numberOfEdges; countEdge++) {
        cin >> from >> to;
        graph->setEdge(from, to);
    }

    vector<vector<int>> ccs = graph->SCC();
    out << ccs.size() << "\n";
    for(auto & cc : ccs) {
        for(int j : cc) {
            out << j << " ";
        }
        out << "\n";
    }
}

void resolveDijkstra() {
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    int numberOfNodes, numberOfEdges, from, to, cost;

    in >> numberOfNodes >> numberOfEdges;

    auto* graph = new Graph(numberOfNodes);

    for (int countEdge = 1; countEdge <= numberOfEdges; countEdge++) {
        in >> from >> to >> cost;
        graph->setEdgeCost(from, to, cost);
    }

    vector<int> distance = graph->Dijkstra(1, 200001);

    //distance[1] it's the node where the alg started so it's value is 0
    for(int node = 2; node <= numberOfNodes; node++){
        if (distance[node] != 20001){
            out << distance[node] << " ";
        } else {
            out << 0 << " ";
        }
    }
}

int main() {
    resolveDijkstra();

    return 0;
}

void Graph::displayEdges() {
    for(int node = 1; node <= numberOfNodes; node ++) {
        for (auto edge: edges[node])
            cout << node << " " << edge << endl;
    }
}

Graph::Graph(int numberOfNodes) {
    this->numberOfNodes = numberOfNodes;
    edges.resize(numberOfNodes + 1);
    edgesCost.resize(numberOfNodes + 1);
}

Graph::~Graph() = default;

void Graph::setEdge(int from, int to) {
    edges[from].push_back(to);
}

void Graph::setEdgeCost(int from, int to, int cost) {
    edgesCost[from].emplace_back(to, cost);
}

vector<int> Graph::distance(int from) {
    queue<int> queue;
    vector<int> visited(numberOfNodes + 1, -1);

    visited[from] = 0;
    queue.push(from);

    while (!queue.empty()) {
        int node = queue.front();
        for (auto edge : edges[node]) {
            if (visited[edge] == -1) {
                visited[edge] = visited[node] + 1;
                queue.push(edge);
            }
        }
        queue.pop();
    }

    return visited;
}

void Graph::DFS(unordered_map<int, bool> &visited, int start) {
    visited[start] = true;

    for(int &node : edges[start]) {
        if(!visited[node]) {
            DFS (visited ,node);
        }
    }
}

int Graph::numberOfComponents() {
    unordered_map<int ,bool> visited;
    int nrOfComp = 0;

    for(int node = 1; node <= numberOfNodes; node ++) {
        if(visited[node] == 0) {
            nrOfComp ++;
            DFS(visited, node);
        }
    }
    return nrOfComp;
}

vector<vector<int>> Graph::SCC() {
    stack<int> stack;
    vector<int> ids(numberOfNodes + 1), low_link(numberOfNodes + 1);
    vector<vector<int>> scc;
    unordered_map<int ,bool> visited, onStack;
    int id = 1;

    for(int node = 1; node <= numberOfNodes; node++){
        if(!visited[node])
            tarjan(node,  id, ids, low_link, stack, onStack, visited, scc);
    }
    return scc;
}

void Graph::tarjan(int start, int &id, vector<int> &ids, vector<int> &low_link,
                   stack<int>& stack, unordered_map<int ,bool> &onStack,
                   unordered_map<int, bool> &visited,vector<vector<int>> &scc) {
    ids[start] = id;
    low_link[start] = id;
    stack.push(start);
    visited[start] = true;
    onStack[start] = true;
    id++;

    for(auto node : edges[start]) {
        if(!visited[node]) {
            tarjan(node, id, ids, low_link, stack, onStack, visited, scc);
            //we min the low_link of the current node, this will make the low values to propagate
            //thorough cycles
            low_link[start] = min(low_link[start], low_link[node]);
        } else {
            //when i have nowhere to go from a node because is all
            // neighbours are already visited)
            // if the previous node is on the stack
            //we min the low_link of the current node, this will make the low values to propagate
            //thorough cycles
            if (onStack[node]) {
                low_link[start] = min(low_link[start], low_link[node]);
            }
        }
    }


    //check if the current node started a connected component (current node
    //visited all its neighbours and he started a component)
    if(low_link[start] == ids[start]){
        vector<int> cc;
        int ccNode;
        //pop nodes off until the current node is reached
        do {
            ccNode = stack.top();
            cc.push_back(ccNode);
            stack.pop();
            onStack[ccNode] = false;
        } while(ccNode != start);
        scc.push_back(cc);
    }
}

//void Graph::bicomponentsDFS(int start, int parent, unordered_map<int, bool> visited,
//                            stack<int> stack, vector<int> low_link, vector<int> link,
//                            int& noOfBiconnectedComponents , vector<vector<int>>& biconnectedComponents) {
//    link[start] = link[parent] + 1;
//    low_link[start] = link[start];
//    stack.push(start);
//    visited[start] = true;
//
//    for (auto node : edges[start]) {
//        if (visited[node]) {
//            cout << low_link[node] << " --- " << link[start] << endl;
//            if(low_link[start] > link[node])
//                low_link[start] = link[node];
//            cout << low_link[node] << " ---- " << link[start] << endl;
//        } else {
//            bicomponentsDFS(node, start, visited, stack, low_link, link, noOfBiconnectedComponents, biconnectedComponents);
//
//            cout << low_link[node] << " -- " << link[start] << endl;
//            if(low_link[start] > low_link[node])
//                low_link[start] = low_link[node];
//
//            cout << low_link[node] << " - " << link[start] << endl;
//            if(low_link[node] >= link[start]) {
//                cout << " - ";
//                noOfBiconnectedComponents ++;
//                cout << noOfBiconnectedComponents << " - ";
//
//                while(!stack.empty() && stack.top() != node) {
//                    biconnectedComponents[noOfBiconnectedComponents].push_back(stack.top());
//                    stack.pop();
//                }
//                biconnectedComponents[noOfBiconnectedComponents].push_back(stack.top());
//                stack.pop();
//                biconnectedComponents[noOfBiconnectedComponents].push_back(start);
//            }
//        }
//    }
//}
//
//void Graph::biconnectedComponents() {
//    int start = 1, parent = 0, noOfBiconnectedComponents = 0;
//    unordered_map<int, bool> visited;
//    stack<int> stack;
//    vector<int> low_link(numberOfNodes + 1, 0), link(numberOfNodes + 1, 0);
//    vector<vector<int>> biconnectedComponents;
//
//    bicomponentsDFS(start , parent, visited, stack, low_link, link, noOfBiconnectedComponents, biconnectedComponents);
//
//    cout << noOfBiconnectedComponents << "\n";
//    for(int biconnectedComponent = 1; biconnectedComponent <= noOfBiconnectedComponents; biconnectedComponent++) {
//        for(auto elements : biconnectedComponents[biconnectedComponent])
//            cout << elements << " ";
//        cout << "\n";
//    }
//}


void Graph::topologicalSortingDFS(int start, vector<bool>& visited, stack<int>& stack)
{
    visited[start] = true;
	for (int node : edges[start]) {
		if (!visited[node]) {
            topologicalSortingDFS(node, visited, stack);
		}
	}
    //add the output to a stack, so we can efficiently display them
    stack.push(start);
}
//1 3 5 9 4 8 7 6 2
void Graph::topologicalSort()
{
    stack<int> stack;
    vector<bool> visited(numberOfNodes + 1, false);;

    //for all unvisited nodes we make a dfs to determine his subsequence
    for (int node = 1; node < visited.size(); node++) {
        if (!visited[node]) {
            topologicalSortingDFS(node, visited, stack);
        }
    }

    //in the stack the node are added backwards, so the node at the top
    //of the stack is one of the starting nodes and at the bottom of
    //the stack we find one of the dead end nodes
    while (!stack.empty()) {
        cout << stack.top() << " ";
        stack.pop();
    }
}

bool Graph::havelHakimi(vector <int> degrees) {

    while(true) {
        sort(degrees.begin(), degrees.end(), greater<int>());

        //if first elem = 0 => all elements are 0 => graph can be built
        if(degrees[0] == 0) {
            return true;
        }

        //if degree of the largest node is bigger than the no of nodes - 1 => graph cant be built
        if(degrees[0] > degrees.size() - 1) {
            return false;
        }

        int node = degrees[0];
        degrees.erase(degrees.begin() + 0);

        for(int i = 0; i < node; ++i) {
            degrees[i] --;
            if(degrees[i] < 0) {
                return false;
            }
        }
    }
}

vector<int> Graph::Dijkstra(int from, int maximumCOst) {
    // initializare Dijkstra
    vector<bool> visited(numberOfNodes + 1, false);
    vector<int> distance(numberOfNodes + 1, maximumCOst);

    // min-heap
    priority_queue<pair<int, int>, std::vector<pair<int, int>>, std::greater<>> minHeap;

    distance[from] = 0;

    //punem nodul de start in heap
    minHeap.push({distance[from], from});
    //first-> distance
    //second-> node

    while (!minHeap.empty()){
        //the top of the heap is the minEdge by cost after the copy is made we delete it
        pair<int, int> minEdge = minHeap.top();
        minHeap.pop();

        // if we already used the top of the heap we don't make all the calls again
        if (visited[minEdge.second]){
            continue;
        }

        //visit a node only when he gets to the top of the heap
        visited[minEdge.second] = true;
        // pair.first -> distance
        // pair.second -> node

        pair<int, int> nod;
        for(auto& neighbor : edgesCost[minEdge.second]){
            // edgesCost.first -> neighbor
            // edgesCost.second -> the cost of the current node and his neighbor

            if(!visited[neighbor.first]){
                // if it's not visited he's not in the tree

                //we calculate the new distance for the neighbour
                int newDistance = distance[minEdge.second] + neighbor.second;

                //if it's smaller than the actual value than we update it with the new newDistance
                if (newDistance < distance[neighbor.first]){
                    distance[neighbor.first] = newDistance;

                    minHeap.push({distance[neighbor.first], neighbor.first});
                }
            }
        }
    }
    return distance;
}