#include <bits/stdc++.h>
using namespace std;

class minHeapComp{
public:
    bool operator()(pair<int, int> n1, pair<int, int> n2){
        return n1.second > n2.second;
    }
};

struct edge{
    int x,y; //muchia ce uneste x cu y
    int cost;
    int max_flow;
};

class Graph{
private:
        int n; //nr de noduri, nr de muchii, nodul de inceput
        int m; // nr de muchii
        bool type; //0 = neorientat; 1 = orientat
        bool flow; //0 = fara flux; 1 = cu flux
        vector<vector <int>> adj; // adj = adjacent (=liste de vecini)
        vector < vector<int> > comp_nmbr; // folosit la biconexe, vector de vectori ce reprezinta componentele biconexe
        vector < vector<edge> > adj_flow;

public:
    Graph(string fname, bool type, bool flow);

    void BFS(int start);

    void DFS();

    vector<vector<int>> CompTareConexeInit();
    void CTC(int node, int discTime[], int lowTime[], stack<int> *st, bool inStack[], int &nrComp, vector<vector<int>> &res);

    int getNumberOfVertices();

    void biconex();
    void DFS_biconex(int node, int low[], int found[], int parent[], bool visited[], int time,stack <pair<int,int> >& st  );

    void TS(int node, bool visited[], stack<int>& sorted_nodes); //sortare topologica
    void TS_read();

    void APM();

    int MaxFlow(int S, int T, const int MAXFLOW);
    int MaxFlow_Utill(vector<vector<int>> &capacity, int S, int T, vector<int> &parent,vector<vector<int>> &flow, vector<bool> &visited, vector<vector<int>> &residual);

    vector<int> Dijkstra();

    vector<int> BellmanFord();


};
int Graph::getNumberOfVertices()
{
    return n;
}

Graph::Graph(string fname, bool type, bool flow){
    ifstream fin(fname);
    this->type = type;
    this->flow = flow;




    switch(this->type){
case true:
        if(this->flow)
        {
                fin>>this->n>>this->m;
                int x,y,nflow;
                adj_flow.resize(n+1);
                edge e;
                for(int i = 0; i < m; i++)
                {
                    fin>>x>>y>>nflow;
                    e.x = x;
                    e.y = y;
                    e.max_flow = nflow;
                    e.cost = 0;
                    adj_flow[e.x].push_back(e);
                }

        }else{
            fin>>this->n>>this->m;
            int x,y;
            adj.resize(n+1);

            for(int i = 0; i < m; i++)
            {
                fin>>x>>y;
                adj[x].push_back(y);
            }


            }
        break;

case false:
        fin>>this->n>>this->m;
        int x,y;
        adj.resize(n+1);

        for(int i = 0; i < m; i++)
        {
            fin>>x>>y;

                adj[x].push_back(y);
                adj[y].push_back(x);

        }
    break;

    }
    fin.close();
}

vector<int> Graph::BellmanFord(){
    static int INF = 1000000;

    vector<int> dist(this->n + 1, INF);
    queue<int> q;
    vector<bool> in_queue(this->n + 1, 0);
    vector<int> cycle_nbr(this->n + 1, 0);

    bool neg_cycle = 0;
    dist[1] = 0;
    q.push(1);
    in_queue[1] = 1;

    while(!q.empty() && !neg_cycle){
        int curr_node = q.front();
        q.pop();

        in_queue[curr_node] = 0;


        for(auto next_node: this->adj_flow[curr_node]){

            if(dist[curr_node] + next_node.max_flow < dist[next_node.y]){

                if(cycle_nbr[next_node.y] > this->n - 1){
                    neg_cycle = 1;
                    break;

                }else{
                    dist[next_node.y] = dist[curr_node] + next_node.max_flow;
                    q.push(next_node.y);
                    in_queue[next_node.y] = 1;
                    cycle_nbr[next_node.y]++;

                }
            }
        }


    }

    if(neg_cycle){
        dist.clear();
        return dist;
    }

    return dist;



}

vector<int> Graph::Dijkstra(){
    priority_queue<pair<int,int>, vector<pair<int,int>>,minHeapComp> heap;
    vector<bool> visited(this->n + 1);
    vector<int> path(this->n + 1, 0);

    heap.push({1,0});

    while(!heap.empty()){
        pair<int, int> currNode = heap.top();
        heap.pop();

        if(!visited[currNode.first]){
            visited[currNode.first] = true;
            path[currNode.first] = currNode.second;

            for(auto nextNode: adj_flow[currNode.first]){
                heap.push({nextNode.y, currNode.second + nextNode.max_flow});
            }
        }

    }

    return path;

}

void Graph::CTC(int node, int discTime[], int lowTime[], stack<int> *st, bool inStack[], int &nrComp, vector<vector<int>> &res){
    static int time = 1;

    discTime[node] = lowTime[node] = ++time;
    st->push(node);
    inStack[node] = 1;

    for (auto it: adj[node]){
        if(discTime[it] == 0){
            CTC(it, discTime, lowTime, st, inStack, nrComp, res);

            lowTime[node] = min(lowTime[node], lowTime[it]);

        }else if(inStack[it] == 1){
            lowTime[node] = min(lowTime[node], discTime[it]);
            }
    }


    res.resize(nrComp + 1);
    int w = 0;
    if (lowTime[node] == discTime[node])
    {
        while (st->top() != node)
        {
            w = (int) st->top();
            res[nrComp].push_back(w);
            inStack[w] = 0;
            st->pop();
        }
        w = (int) st->top();
        res[nrComp].push_back(w);
        inStack[w] = 0;
        st->pop();
        nrComp++;
    }


}

vector<vector<int>> Graph::CompTareConexeInit(){
    int *discTime = new int[this->n + 1]();
    int *lowTime = new int[this->n + 1]();
    bool *inStack = new bool[this->n +1]();
    stack<int> *st = new stack<int>();
    vector<vector<int>> res;
    res.reserve(this->n + 1);
    int nrComp = 0;

//    for(int i = 1; i <= this->n; i++){
//        discTime[i] = -1;
//        lowTime[i] = -1;
//        inStack[i] = 0;
//    }

    for(int i = 1; i <= this->n; i++){
        if(discTime[i] == 0){
            CTC(i, discTime, lowTime, st, inStack, nrComp, res);
        }
    }

    delete[] discTime;
    delete[] lowTime;
    delete[] inStack;
    delete st;

    res.shrink_to_fit();

    return res;

}

void Graph::APM(){
    ifstream fin("apm.in");
    fin>>n>>m;
    vector<pair<int,int>> apm_adj[20010];
    int x,y,c;

    for(int i = 0; i < m; i++){
        fin>>x>>y>>c;
        apm_adj[x].push_back(make_pair(y,c));
        apm_adj[y].push_back(make_pair(x,c));

    }
    fin.close();

// debug stuff
//    for(int v = 1; v <= n; v++){
//        for(unsigned int j = 0; j< apm_adj[v].size(); j++ ){
//            cout<<v<<": "<<apm_adj[v][j].first<< " "<<apm_adj[v][j].second<<",\n";
//        }
//        cout<<"\n";
//    }

    priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;
    vector<bool> inAPM(n+1,false);
    vector<int> weight(n+1, 1100);
    vector<int> parent(n+1,-1);

    int start = 1;
    int s = 0;
    pq.push(make_pair(0,start));
    weight[start] = 0;
    while (!pq.empty()){

        int u = pq.top().second;

        pq.pop();
        if(inAPM[u] == true){
            continue;
        }
        inAPM[u] = true;


        for (auto x : apm_adj[u]){
            int v = x.first;
            int w = x.second;

            if(inAPM[v] == false && w < weight[v]){
                weight[v] = w;
                pq.push(make_pair(weight[v],v));
                parent[v] = u;
            }
        }
    }
    ofstream fout("apm.out");
    for(int i = 2; i <=n; i++){
        s+=weight[i];
    }
    fout<<s<<"\n"<<n-1<<"\n";

        for(int i = 2; i <=n; i++){
        fout<<parent[i] <<" "<<i<<"\n";
    }






}

void Graph::TS_read(){

    if (!this->type){
        cout<<("Topological sorting works only on oriented graphs!\n");
        exit(NULL);
    }

    stack<int> sorted_nodes;
    bool* visited = new bool[n+1];

    for(int i = 0; i <= n; i++){
        visited[i] = false;
    }

    for(int i = 1; i <= n; i++){
        if(!visited[i]){
            TS(i, visited, sorted_nodes);
        }

    }
    ofstream fout("sortaret.out");
    while(!sorted_nodes.empty()){
        fout<<sorted_nodes.top()<<" ";
        sorted_nodes.pop();
    }
    fout.close();
}

void Graph::TS(int node, bool visited[], stack<int>& sorted_nodes){
    visited[node] = true;

    for(auto it: adj[node]){
        if(!visited[it]){
            TS(it, visited, sorted_nodes);
        }

    }
    sorted_nodes.push(node);
}

void Graph::biconex(){

    if (this->type){
        cout<<("Biconex components exist only in unoriented graphs!\n");
        exit(NULL);
    }

    stack < pair<int,int> > st;
    int *found = new int[n+1];
    int *low = new int[n+1];
    int *parent = new int[n+1];
    bool visited[n+1] = {0};
    int time = 0;

    for (int i = 1; i <= n; i++){
        found[i] = -1;
        low[i] = -1;
        parent[i] = -1;
    }

    for (int i = 1; i <= n; i++){
        if (visited[i] == false){
            DFS_biconex(i, low, found, parent, visited, time, st);
        }

    }
    ofstream fout("biconex.out");
    fout<<comp_nmbr.size()<<"\n";

    for(auto comp : comp_nmbr){
        for(auto node: comp){
            fout<<node<<" ";
        }
        fout<<"\n";
    }
    fout.close();

}

void Graph::DFS_biconex(int node, int low[], int found[], int parent[], bool visited[], int time,stack <pair<int,int> >& st  ){
    found[node] = time + 1; //timpul de descoperire in dfs
    low[node] = time + 1;
    time++;
    visited[node] = 1;
    int children = 0;

    for(int i: adj[node] ){

        if (visited[i] == false){
            children++;
            st.push({node,i});
            parent[i] = node;
            DFS_biconex(i, low, found, parent, visited, time, st);
            low[node] = min(low[node], low[i]);

            if( (parent[node] == -1 && children > 1) || (found[node] != -1 && low[i] >= found[node] ) )
            {       /*^radacina                                ^restul nodurilor*/
                vector <int> components; // vector ajutator in care va fi stocata componenta biconexa curenta
                while(st.top().first != node && st.top().second != i){
                        components.push_back(st.top().second);
                        st.pop();
                }
                components.push_back(st.top().second);
                components.push_back(st.top().first);
                st.pop();
                comp_nmbr.push_back(components);

            }

        }else if (parent[node] != i && found[i] < low[node]  ){
                    low[node] = found[i];
                }
    }

}


void Graph::DFS(){
    bool visited[n+1] = {0};
    queue<int> q;
    int conex = 0;

    for(int i = 1; i < n+1; i++){
        if(!visited[i]){
            conex++;
            q.push(i);
            while( !q.empty() ){
                int curr_node = q.front();
                visited[curr_node] = 1;
                q.pop();
                for(unsigned int j = 0; j < adj[curr_node].size(); j++){
                    if(!visited[ adj[ curr_node][j] ] )
                        q.push(adj[curr_node][j] );
                }
            }
        }
    }
    ofstream fout("dfs.out");
    fout<<conex;
    fout.close();

}


void Graph::BFS(int start){
    bool visited[n+1];
    int length[n+1];

    for(int i = 0; i < n+1; i++){
        visited[i] = false;
        length[i] = -1;
    }

    visited[start] = true;
    length[start] = 0;

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

    while(!q.empty()){
        int curr_node = q.front();
        q.pop();
        int nr_vec = adj[curr_node].size();

        for(int i = 0; i<nr_vec;i++){
            int x = adj[curr_node][i];

            if(!visited[x]){
                visited[x] = true;
                q.push(x);
                length[x] = length[curr_node] + 1;
            }
        }
    }

    ofstream fout("bfs.out");
    for(int i = 1; i <= n; i++){
        fout<<length[i]<<" ";
    }
    fout.close();
}


int Graph::MaxFlow(int S, int T, const int MAXFLOW){
    vector<bool> visited(n+1,0);
    vector<int> parent(n+1,0);
    vector< vector<int> > residual(n+1);
    vector <vector<int> > capacity(n+1,vector<int>(n+1, 0));
    vector <vector<int> > flow(n+1,vector<int>(n+1, 0));

    for(int i = 0; i < adj_flow.size(); i++)
    {
        for(int j = 0; j <adj_flow[i].size(); j++)
        {
            residual[i].push_back(adj_flow[i][j].y);
            residual[adj_flow[i][j].y].push_back(i);

            capacity[i][adj_flow[i][j].y] = adj_flow[i][j].max_flow;
        }
    }


    int result = 0;

    while(this->MaxFlow_Utill(capacity, S, T, parent, flow, visited, residual) )
    {
        for(int i : residual[T])


            if(visited[i] && flow[i][T] < capacity[i][T])
            {

                parent[T] = i;
                int path_flow = MAXFLOW;

                for(int u = T; u != S; u = parent[u])
                {
                    int v = parent[u];
                    path_flow = min(path_flow, capacity[v][u] - flow[v][u]);
                }

                if(path_flow > 0)
                {
                        for(int u = T; u != S; u = parent[u])
                        {
                            int v = parent[u];
                            flow[v][u] += path_flow;
                            flow[u][v] -= path_flow;
                        }
                    result += path_flow;
                }
            }
    }
    return result;
}

int Graph::MaxFlow_Utill(vector<vector<int>> &capacity, int S, int T, vector<int> &parent,vector<vector<int>> &flow, vector<bool> &visited, vector<vector<int>> &residual){
    parent.assign(adj_flow.size(), 0);
    visited.clear();
    visited.resize(adj_flow.size(),0);

    queue<int> BFSq;
    BFSq.push(S);

    visited[S] = 1;
    parent[S] = -1;

    while(!BFSq.empty() && !parent[T] )
    {
        int u = BFSq.front();
        BFSq.pop();

        for(int v : residual[u])
        {
            if(capacity[u][v] > flow[u][v] && !visited[v])
            {
                parent [v] = u;
                visited[v] = 1;
                BFSq.push(v);
            }
        }

    }
    return parent[T];

}


int main()
{
    Graph g("bellmanford.in",1,1);
    ofstream fout("bellmanford.out");

    vector<int> res = g.BellmanFord();

    if(res.empty()){
        fout<<"Ciclu negativ!";
    }else{
    for(int i = 2; i < res.size(); i++)
        fout<<res[i]<<' ';
    }



    fout.close();

    return 0;
}

//    vector<int> res = g.Dijkstra();
//
//    for(int i = 2; i < res.size(); i++)
//        fout<<res[i]<<' ';
//
//    fout.close();