#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <sys/resource.h>
using namespace std;

struct edge
{
    int node;
    int neighbour;
    int cost;

};

class Graph {
    int nrNodes; //number of nodes
    vector<vector<edge>> edges; // list of connections between nodes
public:
    Graph(int _nrNodes);
    int getNrNodes() const;
    void setEdge(int node, int neighbour, int cost);
    void printEdges() const;
    const vector<edge>& getNeighbours(int node);
    virtual ~Graph() = default;

    int nrConnectedComponents();
    vector<int> minDistanceBFS(int start);
    vector<int> PrimMST(int& costMST);
    vector<int> Dijkstra();
    vector<int> BellmanFord();

private:
    void DFS(int node, vector<int>& visited);
};
//---------------------------------------------------------
Graph::Graph(int _nrNodes)
{
    this -> nrNodes = _nrNodes;
    this -> edges.resize(_nrNodes+1);
    /*
     * Nodes start at 1, but index starts at 0
     */
}

int Graph::getNrNodes() const
{
    return this -> nrNodes;
}

void Graph::setEdge(int node, int neighbour, int cost)
{
    struct edge tmp;
    tmp.neighbour = neighbour;
    tmp.cost = cost;
    this -> edges[node].push_back(tmp);
}

const vector<edge>& Graph::getNeighbours(int node)
{
    return this -> edges[node];
}

int Graph::nrConnectedComponents()
{
    int ans = 0;
    vector<int> visited(this -> nrNodes+1, 0);
    for(int i = 1 ; i <= this -> nrNodes; i++)
        if(visited[i] == 0)
        {
            DFS(i, visited);
            ++ans;
        }
    return ans;
}

vector<int> Graph::minDistanceBFS(int start)
{
    vector<int>distances(this->nrNodes + 1, -1);
    distances[start] = 0;

    queue<int>toBeVisited;
    toBeVisited.push(start);

    while(!toBeVisited.empty())
    {
        int x = toBeVisited.front();
        toBeVisited.pop();

        for(auto &it: this->edges[x])
            if(distances[it.neighbour] == -1)
            {
                distances[it.neighbour] = distances[x] + 1;
                toBeVisited.push(it.neighbour);
            }

    }     //while loop ended

    return distances;
}

vector<int> Graph::PrimMST(int& costMST)
{
    vector<int> parent(this->nrNodes+1, 0);
    vector<int> minCost(this->nrNodes+1, INT_MAX);
    vector<bool> inMST(this -> nrNodes+1, false);
    priority_queue<pair<int, int>,vector<pair<int, int>> ,greater<>>edgePQ;
    minCost[1] = 0;
    edgePQ.push(make_pair(0, 1)); //cost has to be first for greater<> to work

    while(!edgePQ.empty())
    {
        int currCost = edgePQ.top().first;
        int node = edgePQ.top().second;
        edgePQ.pop();

        if(inMST[node])
            continue;

        inMST[node] = true;
        costMST += currCost;

        for(auto& it: edges[node])
        {
            int neighbour = it.neighbour;
            int cost = it.cost;
            if(!inMST[neighbour] && minCost[neighbour] > cost)
            {
               minCost[neighbour] = cost;
               parent[neighbour] = node;
               edgePQ.push(make_pair(minCost[neighbour], neighbour));
            }
        }
    }
    return parent;
}

void Graph::DFS(int start, vector<int>& visited)
{
    visited[start] = 1;
    for(auto &it: this ->edges[start])
    {
        int neighbour = it.neighbour;
        if(visited[neighbour] == 0)
        {
            visited[neighbour] = 1;
            DFS(neighbour, visited);
        }
    }
}
vector<int> Graph::Dijkstra()
{
    vector<int> minCost(this->nrNodes+1, INT_MAX);
    vector<bool> inMST(this -> nrNodes+1, false);
    priority_queue<pair<int, int>,vector<pair<int, int>> ,greater<>>edgePQ;
    minCost[1] = 0;
    edgePQ.push(make_pair(0, 1)); //cost has to be first for greater<> to work

    while(!edgePQ.empty())
    {
        int node = edgePQ.top().second;
        edgePQ.pop();

        if(inMST[node])
            continue;

        inMST[node] = true;

        for(auto& it: edges[node])
        {
            int neighbour = it.neighbour;
            int cost = it.cost;
            if(!inMST[neighbour] && minCost[node] + cost < minCost[neighbour])
            {
                minCost[neighbour] = minCost[node] + cost;
                edgePQ.push(make_pair(minCost[neighbour], neighbour));
            }
        }
    }
    return minCost;
}

vector<int> Graph::BellmanFord()
{
    vector<int> minCost(this->nrNodes+1, INT_MAX);
    queue<int> activeNodes;
    vector<bool> inQueue(this ->nrNodes+1, false);
    vector<int> nodeOptimizations(this->nrNodes+1, 0);
    minCost[1] = 0;
    activeNodes.push(1);
    inQueue[1] = true;
    nodeOptimizations[1] = 1;

    while(!activeNodes.empty())
    {
        int node = activeNodes.front();
        activeNodes.pop();
        inQueue[node] = false;

        for(auto& it: this -> edges[node])
        {
            int neighbour = it.neighbour;
            int cost = it.cost;
            if(minCost[node] + cost < minCost[neighbour])
            {
                minCost[neighbour] = minCost[node] + cost;
                if(!inQueue[neighbour])
                {
                    activeNodes.push(neighbour);
                    inQueue[neighbour] = true;
                    nodeOptimizations[neighbour]++;
                }
                if(nodeOptimizations[neighbour] >= this->nrNodes)
                    return {-1};

            }
        }
    }

    return minCost;
}

void Graph::printEdges() const
{
  for(int i = 1; i <= this->getNrNodes(); i++)
  {
      cout << i<< ": ";
      for(auto &it: edges[i])
          cout << it.neighbour<< " ";
      cout << "\n";
  }
}
//----------------------------------------------------------
class UndirectedGraph: public Graph{
public:
    UndirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour, int cost);
    ~UndirectedGraph() = default;

    vector<vector<int>> biconnectedComponents();
    vector<vector<int>> criticalEdges();
    bool havelHakimi(vector<int>degrees);

private:
    void biconnectedDFS(int node, int father, vector<int>& lowestLink,
                        vector<int>& nodeID, stack<int>& nodeStack,
                        vector<vector<int>>& bcc);

    void addBiconnected(stack<int>& nodeStack, int node, int neighbour,
                        vector<vector<int>>& bcc);

    void criticalEdgeDFS(int node, int father,vector<int>& lowestLink,
                         vector<int>& nodeID, vector<vector<int>>& critical);
};
//----------------------------------------------------------
UndirectedGraph::UndirectedGraph(int _nrNodes): Graph(_nrNodes){}

void UndirectedGraph::addEdge(int node, int neighbour, int cost)
{
    this -> setEdge(node, neighbour, cost);
    this -> setEdge(neighbour, node, cost);
}

vector<vector<int>> UndirectedGraph::biconnectedComponents()
{
    vector<vector<int>> bcc;
    stack<int> nodeStack;
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);

    for(int node = 1; node <= this -> getNrNodes(); node++)
    {
        if (nodeID.at(node) == -1)
            biconnectedDFS(node, 0, lowestLink,
                           nodeID, nodeStack, bcc);
    }
    return bcc;
}

void UndirectedGraph::biconnectedDFS(int node, int father,
                                     vector<int>& lowestLink,
                                     vector<int>& nodeID,
                                     stack<int>& nodeStack,
                                     vector<vector<int>>& bcc)
{
    nodeID[node] = nodeID[father]+1;
    lowestLink[node] = nodeID[father]+1;
    nodeStack.push(node);

    for (auto &it: this->getNeighbours(node))
    {
        int neighbour = it.neighbour;
        if (nodeID[neighbour] != -1 && neighbour != father)
            lowestLink[node] = min(lowestLink[node], nodeID[neighbour]);

        else if (neighbour != father)
        {
            biconnectedDFS(neighbour, node,
                           lowestLink, nodeID,
                           nodeStack, bcc);
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);

            if (lowestLink[neighbour] >= nodeID[node]) //node is an articulation point
                addBiconnected(nodeStack, node, neighbour, bcc);
        }

    }
}
void UndirectedGraph::addBiconnected(stack<int>& nodeStack, int node,
                                     int neighbour, vector<vector<int>>& bcc)
{
    /*
     * we stop popping at neighbour because between
     * neighbour and node (child and parent) there
     * might be other children of parent.
     * we then add neighbour and node to component
     * leaving node on stack as it might be part of
     * other components
     */
    vector<int>component;
    while (nodeStack.top() != neighbour)
    {
        component.push_back(nodeStack.top());
        nodeStack.pop();
    }
    nodeStack.pop();
    component.push_back(neighbour);
    component.push_back(node);
    bcc.push_back(component);
}

vector<vector<int>> UndirectedGraph::criticalEdges()
{
    vector<vector<int>> critical;
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);
    for(int node = 0; node < this -> getNrNodes(); ++node)
        if(nodeID[node] == -1)
        {
            criticalEdgeDFS(node, 0, lowestLink, nodeID,critical);
        }

    return critical;
}

void UndirectedGraph::criticalEdgeDFS(int node, int father,
                                      vector<int>& lowestLink,
                                      vector<int>& nodeID,
                                      vector<vector<int>>& critical)
{
    nodeID[node] = nodeID[father]+1;
    lowestLink[node] = nodeID[father]+1;

    for (auto &it: this->getNeighbours(node))
    {
        int neighbour = it.neighbour;
        if (nodeID[neighbour] == -1 && neighbour != father)
        {
            criticalEdgeDFS(neighbour, node, lowestLink,
                            nodeID,critical);
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);

            if (lowestLink[neighbour] > nodeID[node]) //node is an articulation point
                critical.push_back({node, neighbour});
        }
        else if (neighbour != father)
            lowestLink[node] = min(lowestLink[node], nodeID[neighbour]);
    }
}

bool UndirectedGraph::havelHakimi(vector<int> degrees)
{
    int loops = 0;
    while(true)
    {
        sort(degrees.begin(), degrees.end(), greater<>());

        if(degrees[0] == 0)
            return true;

        if(degrees[0] > degrees.size() - loops)
            return false;

        for(int i = 1; i <= degrees[0]; ++i)
            if(--degrees[i] < 0)
                return false;
        degrees[0] = 0;
        loops++;
    }
}
//--------------------------------------------------------------------

class DirectedGraph: public Graph {
public:
    DirectedGraph(int _nrNodes);
    void addEdge(int node, int neighbour, int cost);
    ~DirectedGraph() = default;

    vector<vector<int>> getStronglyConnected();
    vector<int> topologicalSorting();

private:

    void TarjanDFS(int start, int& counterID,
                          stack<int>& nodeStack, vector<bool>& onStack,
                          vector<vector<int>>& scc,
                          vector<int>& nodeID, vector<int>& lowestLink);

    void topologicalDFS(int node, vector<int>& sorted,
                        vector<bool>& visited);

};
//-----------------------------------------------------------

DirectedGraph::DirectedGraph(int _nrNodes): Graph(_nrNodes) {}

void DirectedGraph::addEdge(int node, int neighbour, int cost)
{
   this -> setEdge(node, neighbour, cost);
}

vector<vector<int>> DirectedGraph::getStronglyConnected()
{ // initializing everything we need for the Tarjan algorithm
    vector<vector<int>> scc;
    stack<int> nodeStack;
    vector<bool> onStack(this -> getNrNodes()+1, false);
    vector<int> lowestLink(this -> getNrNodes()+1, -1);
    vector<int> nodeID(this -> getNrNodes()+1, -1);
    int counterID = 0;

    for(int node = 1; node <= this -> getNrNodes(); ++node)
        if(nodeID[node] == -1)
            TarjanDFS(node, counterID, nodeStack,
                      onStack, scc, nodeID, lowestLink);
    /*
     * scc = strongly connected component
     * TarjanDFS() modifies vector<vector<int>> scc
     * so vector<vector<int>> scc will contain all the needed components
     */

    return scc;
}

void DirectedGraph::TarjanDFS(int node, int& counterID,
                              stack<int>& nodeStack,
                              vector<bool>& onStack,
                              vector<vector<int>>& scc,
                              vector<int>& nodeID,
                              vector<int>& lowestLink)
{
    vector<int> component;
    nodeID[node] = counterID;
    lowestLink[node] = counterID++;
    nodeStack.push(node);
    onStack[node] = true;

    for(auto &it: this->getNeighbours(node))
    {
        int neighbour = it.neighbour; // node -> first; cost -> second
        if(nodeID[neighbour] == -1)         // if neighbour not visited
            TarjanDFS(neighbour, counterID, nodeStack,
                      onStack, scc, nodeID,
                      lowestLink);
        if(onStack[neighbour])          //if neighbour is on stack
            lowestLink[node] = min(lowestLink[node], lowestLink[neighbour]);
    }

    if(lowestLink[node] == nodeID[node])  // if this is true then node is the beginning of a scc
    {
        while(!nodeStack.empty())
        {
            int nodeToPop = nodeStack.top();
            component.push_back(nodeToPop);
            onStack[nodeToPop] = false;
            nodeStack.pop();
            if(nodeToPop == node)
                break;
        }

        scc.push_back(component);
        component.clear();
    }
}

vector<int> DirectedGraph::topologicalSorting()
{
    vector<int> sorted;
    vector<bool> visited(this->getNrNodes() + 1, false);
    for(int node = 1; node < visited.size(); ++node)
        if(!visited[node])
            topologicalDFS(node, sorted, visited);
    /*
     * -> TopologicalDFS() modifies the sorted vector
     * -> the sorted nodes are the nodes' times in descending order
     */
    return sorted;
}

void DirectedGraph::topologicalDFS(int node, vector<int>&sorted,
                                   vector<bool>&visited)
{
   visited[node] = true;
   for(auto &it: this->getNeighbours(node))
   {
       int neighbour = it.neighbour;
       if (!visited[neighbour])
           topologicalDFS(neighbour, sorted, visited);

   }
   sorted.push_back(node);
}

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

void DFS_INFO_ARENA()
{
    ifstream fin("dfs.in");
    ofstream fout("dfs.out");
    int n, m, x, y;
    fin >> n >> m;
    UndirectedGraph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        ug.addEdge(x, y, 0);
    }
    fout << ug.nrConnectedComponents();
}
void BFS_INFO_ARENA()
{
    ifstream fin("bfs.in");
    ofstream fout("bfs.out");
    int n, m, x, y, s;
    fin >> n >> m >> s;
    DirectedGraph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        dg.addEdge(x, y, 0);
    }
    vector<int> ans = dg.minDistanceBFS(s);
    for(int i = 1 ; i <= dg.getNrNodes(); i++)
        fout << ans[i] << " ";
}
void SCC_INFO_ARENA()
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    int n, m, x, y;
    fin >> n >> m;
    DirectedGraph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        dg.addEdge(x, y, 0);
    }
    vector<vector<int>> scc = dg.getStronglyConnected();
    fout << scc.size()<< "\n";

    for(auto &comp: scc)
    {
        for(auto &elem: comp)
            fout << elem << " ";
        fout << "\n";
    }
}
void TOPOLOGICAL_SORT_INFO_ARENA()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");
    int n, m, x, y;
    fin >> n >> m;
    DirectedGraph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        dg.addEdge(x, y, 0);
    }
    vector<int> ans = dg.topologicalSorting();
    for(int i = ans.size()-1; i >= 0; i--)
        fout << ans.at(i)<< " ";

}
void BCC_INFO_ARENA()
{
    const rlim_t new_stackSize = 20000000;
    struct rlimit limit;
    getrlimit(RLIMIT_STACK, &limit);
    limit.rlim_cur = new_stackSize;
    setrlimit(RLIMIT_STACK, &limit);

    ifstream fin("biconex.in");
    ofstream fout("biconex.out");
    int n, m, x, y;
    fin >> n >> m;
    UndirectedGraph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        ug.addEdge(x, y, 0);
    }
    vector<vector<int>> ans = ug.biconnectedComponents();

    fout << ans.size()<< " ";
    for(auto &comp: ans)
    {
        for(auto &elem: comp)
            fout << elem << " ";
        fout << "\n";
    }
}
vector<vector<int>> CRITICAL_CONN_LEETCODE(int n, vector<vector<int>>& connections)
{
    UndirectedGraph ug(n);
    int m = connections.size();
    for(int i = 0; i < m ; ++i)
        ug.addEdge(connections[i][0], connections[i][1], 0);

    return ug.criticalEdges();

}
void HAVEL_HAKIMI()
{
    int n, d;
    cin >> n;
    UndirectedGraph ug(n);
    vector<int>degrees;
    for(int i = 0; i < ug.getNrNodes(); i++)
    {
        cin >> d;
        degrees.push_back(d);
    }
    cout << ug.havelHakimi(degrees);
}
void MIN_SPANNING_TREE_INFO_ARENA()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, x, y, c;
    fin >> n >> m;
    Graph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y>> c;
        ug.setEdge(x, y, c);
        ug.setEdge(y, x, c);
    }
    int costMST = 0;
    vector<int> ans = ug.PrimMST(costMST);

    fout << costMST << "\n";
    fout << n - 1 << "\n";
    for(unsigned i = 2; i < ans.size(); i++)
        fout<< ans[i] << " "<< i << "\n";

}

void DIJKSTRA_INFO_ARENA()
{
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    int n, m, x, y, c;
    fin >> n >> m;
    Graph dg(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y>> c;
        dg.setEdge(x, y, c);
    }

    vector<int> ans = dg.Dijkstra();
    for(unsigned i = 2; i < ans.size(); i++)
         if(ans[i] != INT_MAX)
          fout << ans[i]<< " ";
        else
          fout << 0 << " ";
}
void BELLMAN_FORD_INFO_ARENA()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int n, m, x, y, c;
    fin >> n >> m;
    Graph ug(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y>> c;
        ug.setEdge(x, y, c);
    }

    vector<int> ans = ug.BellmanFord();
    if(ans[0] == -1)
        fout << "Ciclu negativ!";
    else
    for(unsigned i = 2; i < ans.size(); i++)
        fout << ans[i]<< " ";
}
int main()
{
    DIJKSTRA_INFO_ARENA();
    return 0;

}