#include <bits/stdc++.h>
#include <iostream>
#include <climits>
#include <fstream>
using namespace std;
ifstream f("intrare.in");
ofstream g("maxflow.out");
class graf
{
    private:
        int n;
        vector<vector< int > > vecini;
        int grad_int[100001];
        int grad_ext[100001];
    public:
        graf(int n);
        void citire_graf_orientat(int m);
        void citire_graf_neorientat(int m);
        void BFS(int start);
        void DFS(int start, bool vizitat[]);
        void DFS_cu_numarare(int start, bool vizitat[],int distanta[]);
        int nr_comp_conexe();
        void sortare_topologica();
        void ctc();
        void DFS2(int start, int vizitat[], stack <int>& stiva);
        void DFS_Transpus(int start, int vizitat[],vector <vector<int> > vecini_transpus,vector <vector<int> >& rezultat, int &Nr_comp_tare_conexe);
        void Componente_Biconexe();
        void DFS3(int start,int tata[], bool vizitat[], stack <pair <int,int> > &stiva_muchii, int nivel[],int nivel_minim[],vector<vector< int > >&solutie,int nivel_curent);
        void Muchii_Critice();
        void DFS_MC(int start,int tata[], bool vizitat[], stack <pair <int,int> > &stiva_muchii, int nivel[],int nivel_minim[],vector<pair <int,int> >&solutie,int nivel_curent);
        void reuniune(int nod1,int nod2, vector<int> &parinte,vector<int> &dim_multime);
        int gaseste_parinte(int nod, vector<int> &parinte);
        void paduri_multimi_disjuncte();
        int diametru_arbore();
        bool BFS_flux_maxim(int start, int destinatie, vector<int>& parinte, vector<bool>& vizitat,const vector< vector<int> >& flux,const vector< vector<int> >& capacitate);
        int flux_maxim(int m);
};
graf :: graf(int N)
{
    n=N;
    vecini.resize(n+1);
    for(int i=1;i<=n;i++){
        grad_int[i]=0;
        grad_ext[i]=0;
    }
}
void graf :: citire_graf_orientat(int M)
{
    int a,b;
    for(int i=1;i<=M;i++){
        f>>a>>b;
        grad_ext[a]++;
        grad_int[b]++;
        vecini[a].push_back(b);
    }
}
void graf :: citire_graf_neorientat(int m)
{
    int a,b;
    for(int i=1;i<=m;i++){
        f>>a>>b;
        grad_ext[a]++;
        grad_ext[b]++;
        grad_int[a]++;
        grad_int[b]++;
        vecini[a].push_back(b);
        vecini[b].push_back(a);
    }
}
void graf :: BFS(int start)
{
    queue <int> coada;
    int distanta[n+1];
    for(int i=1;i<=n;i++){
        distanta[i]=-1;
    }
    coada.push(start);
    distanta[start]=0;
    while(coada.empty()==0){
        for(int i=0;i<int(vecini[coada.front()].size());i++){
            if(distanta[vecini[coada.front()][i]]==-1){
                coada.push(vecini[coada.front()][i]);
                distanta[vecini[coada.front()][i]]=distanta[coada.front()]+1;
            }
        }
        coada.pop();
    }
    for(int i=1;i<=n;i++){
        g<<distanta[i]<<" ";
    }
}
int graf :: nr_comp_conexe()
{
    bool vizitat[n+1];
    int Nr=0;
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    for(int i=1;i<=n;i++){
        if(vizitat[i]==0){
            Nr++;
            DFS(i, vizitat);
        }
    }
    return Nr;
}
void graf :: DFS(int start, bool vizitat[])
{
    vizitat[start]=1;
    for(int i=0;i<int(vecini[start].size());i++){
        if(vizitat[vecini[start][i]]==0){
            vizitat[vecini[start][i]]=1;
            DFS(vecini[start][i],vizitat);
        }
    }
}

void graf :: sortare_topologica()
{
    vector<int> rezolvare;
    bool vizitat[n+1];
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    while(rezolvare.size()<n){
        for(int i=1;i<=n && rezolvare.size()<n;i++){
            if(grad_int[i]==0 && vizitat[i]==0){
                rezolvare.push_back(i);
                vizitat[i]=1;
                for(int j=0;j<int(vecini[i].size());j++){
                    grad_int[vecini[i][j]]--;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        g<<rezolvare[i]<<" ";
    }
}
void graf :: DFS2(int start, int vizitat[], stack <int>& stiva)
{
    vizitat[start]=1;
    for(int i=0;i<int(vecini[start].size());i++){
        if(vizitat[vecini[start][i]]==0){
            vizitat[vecini[start][i]]=1;
            DFS2(vecini[start][i],vizitat,stiva);
        }
    }
    stiva.push(start);
}
void graf :: DFS_Transpus(int start, int vizitat[],vector <vector<int> > vecini_transpus,vector <vector<int> >& rezultat, int &Nr_comp_tare_conexe)
{
    vizitat[start]=2;
    rezultat[Nr_comp_tare_conexe].push_back(start);
    for(int i=0;i<int(vecini_transpus[start].size());i++){
        if(vizitat[vecini_transpus[start][i]]==1){
            DFS_Transpus(vecini_transpus[start][i],vizitat,vecini_transpus,rezultat, Nr_comp_tare_conexe);
        }
    }
}
void graf :: ctc()
{
    vector <vector<int> > rezultat;
    rezultat.resize(n+1);
    stack <int> stiva;
    int vizitat[n+1];
    int Nr_comp_tare_conexe=0;
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    vector <vector<int> > vecini_transpus;
    vecini_transpus.resize(n+1);
    rezultat.resize(n+1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<vecini[i].size();j++){
            vecini_transpus[vecini[i][j]].push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(vizitat[i]==0){
            DFS2(i,vizitat,stiva);
        }
    }
    while(stiva.size()>0){
        if(vizitat[stiva.top()]==1){
            Nr_comp_tare_conexe++;
            DFS_Transpus(stiva.top(),vizitat,vecini_transpus,rezultat, Nr_comp_tare_conexe);
        }
        stiva.pop();
    }
    g<<Nr_comp_tare_conexe<<'\n';
    for(int i=1;i<=Nr_comp_tare_conexe;i++){
        for(int j=0;j<int(rezultat[i].size());j++){
            g<<rezultat[i][j]<<" ";
        }
        g<<'\n';
    }
}
void graf :: Componente_Biconexe()
{
    bool vizitat[n+1];
    int nivel[n+1];
    int nivel_minim[n+1];
    stack <pair <int,int> > stiva_muchii;
    int tata[n+1];

    for(int i=1;i<=n;i++){
        nivel[i]=-1;
    }
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    for(int i=1;i<=n;i++){
        tata[i]=0;
    }
    vector<vector< int > >solutie;
    DFS3(1,tata, vizitat,stiva_muchii, nivel,nivel_minim,solutie,0);
    while(stiva_muchii.size()>0){///aici o sa ramana muchiile critice + cele care leaga noduri "cu un singur vecin"
        vector <int> temporar_noduri;
        temporar_noduri.push_back(stiva_muchii.top().first);
        temporar_noduri.push_back(stiva_muchii.top().second);
        solutie.push_back(temporar_noduri);
        stiva_muchii.pop();
    }
    g<<solutie.size()<<'\n';
    for(int i=0;i<solutie.size();i++){
        for(int j=0;j<solutie[i].size();j++){
            g<<solutie[i][j]<<" ";
        }
        g<<'\n';
    }

}
void graf :: DFS3(int start,int tata[], bool vizitat[], stack <pair <int,int> > &stiva_muchii, int nivel[],int nivel_minim[],vector<vector< int > >&solutie,int nivel_curent)
{
    vizitat[start]=1;
    nivel[start]=nivel_curent;
    nivel_minim[start]=nivel_curent;
    if(vecini[start].size()==1){///aici o sa ramana muchii critice care leaga un nod "cu un singur vecin" de vecinul sau, deci e muchie critica
        vector<int> temporar_noduri;
        temporar_noduri.push_back(stiva_muchii.top().first);
        temporar_noduri.push_back(stiva_muchii.top().second);
        solutie.push_back(temporar_noduri);
        stiva_muchii.pop();
    }
    else{
        for(int i=0;i<int(vecini[start].size());i++){
            if(vizitat[vecini[start][i]]==1 && nivel[vecini[start][i]]<nivel[start] && vecini[start][i] != tata[start]){
                stiva_muchii.push(make_pair(start,vecini[start][i]));
                nivel_minim[start]=min(nivel_minim[start],nivel[vecini[start][i]]+1);
                tata[start]=vecini[start][i];
            }
            else
            if(vizitat[vecini[start][i]]==0){
                tata[vecini[start][i]]=start;
                stiva_muchii.push(make_pair(start,vecini[start][i]));
                DFS3(vecini[start][i],tata,vizitat,stiva_muchii,nivel,nivel_minim,solutie,nivel_curent+1);
                if(nivel_minim[vecini[start][i]] <= nivel[start]){
                    vector<int> temporar_muchii[2];
                    vector<int> temporar_noduri;
                    do{
                        temporar_muchii[0].push_back(stiva_muchii.top().first);
                        temporar_muchii[1].push_back(stiva_muchii.top().second);
                        stiva_muchii.pop();
                    }while(stiva_muchii.top().first!=tata[vecini[start][i]]);
                    temporar_muchii[0].push_back(stiva_muchii.top().first);
                    temporar_muchii[1].push_back(stiva_muchii.top().second);
                    stiva_muchii.pop();
                    for(int j=0;j<temporar_muchii[1].size();j++){
                        temporar_noduri.push_back(temporar_muchii[0][j]);
                    }
                    solutie.push_back(temporar_noduri);
                }
            }
        }
    }
}
void graf :: Muchii_Critice()
{
    bool vizitat[n+1];
    int nivel[n+1];
    int nivel_minim[n+1];
    stack <pair <int,int> > stiva_muchii;
    int tata[n+1];

    for(int i=1;i<=n;i++){
        nivel[i]=-1;
    }
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    for(int i=1;i<=n;i++){
        tata[i]=0;
    }
    vector<pair <int,int> >solutie;
    DFS_MC(1,tata, vizitat,stiva_muchii, nivel,nivel_minim,solutie,0);
    while(stiva_muchii.size()>0){///aici o sa ramana muchiile critice + cele care leaga noduri "cu un singur vecin"
        solutie.push_back(make_pair(stiva_muchii.top().first,stiva_muchii.top().second));
        stiva_muchii.pop();
    }
    g<<"[";
    for(int i=0;i<solutie.size();i++){
        g<<"["<<solutie[i].first<<","<<solutie[i].second<<"]";
        if(i!=solutie.size()-1){
            g<<",";
        }
        else
            g<<"]";
    }

}
void graf :: DFS_MC(int start,int tata[], bool vizitat[], stack <pair <int,int> > &stiva_muchii, int nivel[],int nivel_minim[],vector<pair <int,int> >&solutie,int nivel_curent)
{
    vizitat[start]=1;
    nivel[start]=nivel_curent;
    nivel_minim[start]=nivel_curent;
    if(vecini[start].size()==1){///aici o sa ramana muchii critice care leaga un nod "cu un singur vecin" de vecinul sau, deci e muchie critica
        solutie.push_back(make_pair(stiva_muchii.top().first,stiva_muchii.top().second));
        stiva_muchii.pop();
    }
    else{
        for(int i=0;i<int(vecini[start].size());i++){
            if(vizitat[vecini[start][i]]==1 && nivel[vecini[start][i]]<nivel[start] && vecini[start][i] != tata[start]){
                stiva_muchii.push(make_pair(start,vecini[start][i]));
                nivel_minim[start]=min(nivel_minim[start],nivel[vecini[start][i]]+1);
                tata[start]=vecini[start][i];
            }
            else
            if(vizitat[vecini[start][i]]==0){
                tata[vecini[start][i]]=start;
                stiva_muchii.push(make_pair(start,vecini[start][i]));
                DFS_MC(vecini[start][i],tata,vizitat,stiva_muchii,nivel,nivel_minim,solutie,nivel_curent+1);
                if(nivel_minim[vecini[start][i]] <= nivel[start]){
                    do{
                        stiva_muchii.pop();
                    }while(stiva_muchii.top().first!=tata[vecini[start][i]]);
                    stiva_muchii.pop();
                }
            }
        }
    }
}
bool Havel_Hakimi(vector<int>grade)
{
    sort(grade.begin(),grade.end());
    if(grade[grade.size()-1]>grade.size()-1){
        return false;
    }
    while(grade[0]>=0){
        int cel_cel_mai_mare_grad=grade[grade.size()-1];
        grade.pop_back();
        if(cel_cel_mai_mare_grad>grade.size()){
            return false;
        }
        for(int i=grade.size()-1;i>=0;i--){
            cel_cel_mai_mare_grad--;
            grade[i]--;
            if(cel_cel_mai_mare_grad==0){
                break;
            }
        }
        if(cel_cel_mai_mare_grad!=0){
            return false;
        }
        sort(grade.begin(),grade.end());
        while(*grade.begin()==0 && grade.size()!=0){
            grade.erase(grade.begin());
        }
        if(grade.size()==0 || grade[0]==0){
            return true;
        }
    }
    return false;
}
int graf :: gaseste_parinte(int nod,vector<int> &parinte)
{
    if(parinte[nod]==nod){
        return nod;
    }
    else
    return gaseste_parinte(parinte[nod],parinte);
}
void graf :: reuniune(int nod1,int nod2, vector<int> &parinte,vector<int> &dim_multime)
{
    int parinte1 = gaseste_parinte(nod1,parinte);
    int parinte2 = gaseste_parinte(nod2,parinte);
    if(parinte1==parinte2){
        return;
    }
    else{
        if(dim_multime[parinte1]>dim_multime[parinte2]){
            parinte[parinte2]=parinte1;
            dim_multime[parinte1] = dim_multime[parinte1]+dim_multime[parinte2];
        }
        else{
            parinte[parinte1]=parinte2;
            dim_multime[parinte2] = dim_multime[parinte2]+dim_multime[parinte1];
        }
    }
}
void graf :: paduri_multimi_disjuncte()
{
    int m;
    int a,b,operatie;
    f>>m;
    vector <int> parinte;
    vector <int> dim_multime;
    parinte.resize(n+1);
    dim_multime.resize(n+1,1);
    for(int i=1;i<=n;i++){
        parinte[i]=i;
    }
    for(int i=1;i<=m;i++){
        f>>operatie>>a>>b;
        if(operatie==2){
            if(gaseste_parinte(a,parinte)==gaseste_parinte(b,parinte)){
                g<<"DA"<<'\n';
            }
            else
            g<<"NU"<<'\n';
        }
        else
        if(operatie==1){
            reuniune(a,b,parinte,dim_multime);
        }
    }
}
void graf :: DFS_cu_numarare(int start, bool vizitat[],int distanta[])
{
    vizitat[start]=1;
    for(int i=0;i<int(vecini[start].size());i++){
        if(vizitat[vecini[start][i]]==0){
            vizitat[vecini[start][i]]=1;
            distanta[vecini[start][i]]=distanta[start]+1;
            DFS_cu_numarare(vecini[start][i],vizitat,distanta);
        }
    }
}
int graf :: diametru_arbore()
{
    bool vizitat[n+1];
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    int distanta[n+1];
    for(int i=1;i<=n;i++){
        distanta[i]=0;
    }
    DFS_cu_numarare(1, vizitat, distanta);
    int cel_mai_distant_nod=1;
    int distanta_max=distanta[1];
    for(int i=2;i<=n;i++){
        if(distanta[i]>distanta_max){
            distanta_max=distanta[i];
            cel_mai_distant_nod=i;
        }
    }
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    for(int i=1;i<=n;i++){
        distanta[i]=0;
    }
    DFS_cu_numarare(cel_mai_distant_nod, vizitat, distanta);
    distanta_max=distanta[1]+1;
    for(int i=2;i<=n;i++){
        if(distanta[i]+1>distanta_max){
            distanta_max=distanta[i]+1;
        }
    }
    return distanta_max;
}
bool graf :: BFS_flux_maxim(int start, int destinatie, vector<int>& parinte, vector<bool>& vizitat,const vector< vector<int> >& flux,const vector< vector<int> >& capacitate)
{
    queue <int> coada;
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    coada.push(start);
    vizitat[start]=1;
    while(coada.empty()==0){
        if(coada.front()==destinatie){
            return 1;
        }
        else{
            for(int i=0;i<vecini[coada.front()].size();i++){
                if(vizitat[vecini[coada.front()][i]]==0 && capacitate[coada.front()][vecini[coada.front()][i]]>flux[coada.front()][vecini[coada.front()][i]]){
                    vizitat[vecini[coada.front()][i]]=1;
                    parinte[vecini[coada.front()][i]]=coada.front();
                    coada.push(vecini[coada.front()][i]);
                }
            }
            coada.pop();
        }
    }
    return vizitat[destinatie];
}
int graf :: flux_maxim(int m)
{
    int rezultat=0;
    vector<int> parinte(n+1,0);
    vector<bool> vizitat(n+1,0);
    vector< vector<int> > flux(n+1, vector <int> (n+1, 0));
    vector< vector<int> > capacitate(n+1, vector <int> (n+1, 0));
    int a,b,capac;
    vector<int> vecini_final_de_intors;
    for(int i=1;i<=m;i++){
        f>>a>>b>>capac;
        vecini[a].push_back(b);
        capacitate[a][b]=capac;
        if(b==n){
            vecini_final_de_intors.push_back(a);
        }
    }
    while(BFS_flux_maxim(1, n, parinte, vizitat, flux, capacitate)==1){
        for(int i=0;i<vecini_final_de_intors.size();i++){
            if(capacitate[vecini_final_de_intors[i]][n]-flux[vecini_final_de_intors[i]][n]>0 && vizitat[vecini_final_de_intors[i]]==1)
            {
                parinte[n]=vecini_final_de_intors[i];
                int f_min=INT_MAX;
                for(int nod=n;nod!=1;nod=parinte[nod]){
                    f_min=min(f_min, capacitate[parinte[nod]][nod]-flux[parinte[nod]][nod]);
                }
                if(f_min>0){
                    for(int nod=n;nod!=1;nod=parinte[nod]){
                        flux[parinte[nod]][nod]+=f_min;
                        flux[nod][parinte[nod]]-=f_min;
                    }
                    rezultat+=f_min;
                }
            }
        }
    }
    return rezultat;
}
class graf_cu_costuri
{
    private:
        int n;
        vector<pair<int,pair<int,int> > > muchii;
    public:
        graf_cu_costuri(int n);
        void citire(int m);
        void kruskall();
        void reuniune(int nod1,int nod2, vector<int> &parinte,vector<int> &dim_multime);
        int gaseste_parinte(int nod, vector<int> &parinte);
        void dijkstra(int m);
        void bellman_ford(int m);
};
graf_cu_costuri :: graf_cu_costuri(int n)
{
    this->n=n;
}
void graf_cu_costuri :: citire(int m)
{
    int a,b,cost;
    for(int i=1;i<=m;i++){
        f>>a>>b>>cost;
        muchii.push_back(make_pair(cost,make_pair(a,b)));
    }
    /*
    cout<<"DA"<<endl;
    for(int i=0;i<muchii.size();i++){
        cout<<muchii[i].second.first<<" -> "<<muchii[i].second.second<<" are costul: "<<muchii[i].first<<'\n';
    }
    */
}
int graf_cu_costuri :: gaseste_parinte(int nod,vector<int> &parinte)
{
    if(parinte[nod]==nod){
        return nod;
    }
    else
    return gaseste_parinte(parinte[nod],parinte);
}
void graf_cu_costuri :: reuniune(int nod1,int nod2, vector<int> &parinte,vector<int> &dim_multime)
{
    int parinte1 = gaseste_parinte(nod1,parinte);
    int parinte2 = gaseste_parinte(nod2,parinte);
    if(parinte1==parinte2){
        return;
    }
    else{
        if(dim_multime[parinte1]>dim_multime[parinte2]){
            parinte[parinte2]=parinte1;
            dim_multime[parinte1] = dim_multime[parinte1]+dim_multime[parinte2];
        }
        else{
            parinte[parinte1]=parinte2;
            dim_multime[parinte2] = dim_multime[parinte2]+dim_multime[parinte1];
        }
    }
}
void graf_cu_costuri :: kruskall()
{
    vector <int> parinte;
    vector <int> dim_multime;
    vector <pair<int,int> > solutie;
    parinte.resize(n+1);
    dim_multime.resize(n+1,1);
    for(int i=1;i<=n;i++){
        parinte[i]=i;
    }
    int cost_apm=0;
    sort(muchii.begin(), muchii.end());
    for(int i=0;i<muchii.size();i++){
        if(gaseste_parinte(muchii[i].second.first,parinte)!=gaseste_parinte(muchii[i].second.second,parinte)){
            cost_apm=cost_apm+muchii[i].first;
            solutie.push_back(make_pair(muchii[i].second.first,muchii[i].second.second));
            reuniune(muchii[i].second.first,muchii[i].second.second,parinte,dim_multime);
        }
    }
    g<<cost_apm<<'\n';
    g<<solutie.size()<<'\n';
    for(int i=0;i<solutie.size();i++){
        g<<solutie[i].first<<" "<<solutie[i].second<<'\n';
    }
}
void graf_cu_costuri :: dijkstra(int m)
{
    vector <vector <pair <int, int> > > vecini;
    vecini.resize(n+1);
    int distanta[n+1];
    distanta[1]=0;
    for(int i=2;i<=n;i++){
        distanta[i]=INT_MAX;
    }
    bool vizitat[n+1];
    for(int i=1;i<=n;i++){
        vizitat[i]=0;
    }
    int a,b,cost;
    for(int i=1;i<=m;i++){
        f>>a>>b>>cost;
        vecini[a].push_back(make_pair(b,cost));
    }
    priority_queue <pair<int, int>, vector <pair<int,int> >, greater <pair<int,int> > > Q;
    Q.push(make_pair(0,1));
    while(Q.size()!=0){
        int nod_curent=Q.top().second;
        Q.pop();
        if(vizitat[nod_curent]==0){
            vizitat[nod_curent]=1;
            for(int i=0;i<vecini[nod_curent].size();i++){
                if(distanta[vecini[nod_curent][i].first]>distanta[nod_curent]+vecini[nod_curent][i].second){
                    distanta[vecini[nod_curent][i].first]=distanta[nod_curent]+vecini[nod_curent][i].second;
                    Q.push(make_pair(distanta[vecini[nod_curent][i].first],vecini[nod_curent][i].first));
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(distanta[i]!=INT_MAX){
            g<<distanta[i]<<" ";
        }
        else
        g<<0<<" ";
    }
}
void graf_cu_costuri :: bellman_ford(int m)
{
    vector <vector <pair <int, int> > > vecini;
    vecini.resize(n+1);
    int distanta[n+1];
    distanta[1]=0;
    for(int i=2;i<=n;i++){
        distanta[i]=INT_MAX;
    }
    int nr_de_vizitari[n+1];
    for(int i=1;i<=n;i++){
        nr_de_vizitari[i]=0;
    }
    int a,b,cost;
    for(int i=1;i<=m;i++){
        f>>a>>b>>cost;
        vecini[a].push_back(make_pair(b,cost));
    }
    bool in_coada[n+1];
    for(int i=1;i<=n;i++){
        in_coada[i]=0;
    }
    queue <int> Q;
    Q.push(1);
    in_coada[1]=1;
    while(Q.size()!=0){
        int nod_curent = Q.front();
        Q.pop();
        in_coada[nod_curent]=0;
        nr_de_vizitari[nod_curent]++;
        if(nr_de_vizitari[nod_curent]>n){
            g<<"Ciclu negativ!";
            return;
        }
        for(int i=0;i<vecini[nod_curent].size();i++){
            if(distanta[vecini[nod_curent][i].first]>distanta[nod_curent]+vecini[nod_curent][i].second){
                distanta[vecini[nod_curent][i].first]=distanta[nod_curent]+vecini[nod_curent][i].second;
                if(in_coada[vecini[nod_curent][i].first]==0){
                    Q.push(vecini[nod_curent][i].first);
                    in_coada[vecini[nod_curent][i].first]=1;
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        g<<distanta[i]<<" ";
    }
}
class graf_cu_matricea_ponderilor
{
    private:
        int n;
        int ponderi[101][101];
    public:
        void citire();
        void floyd_warshall();
};
void graf_cu_matricea_ponderilor::citire()
{
    f>>this->n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f>>ponderi[i][j];
        }
    }
}
void graf_cu_matricea_ponderilor::floyd_warshall()
{
    int drum[n+1][n+1];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(ponderi[i][j]!=0){
                drum[i][j]=ponderi[i][j];
            }
            else
            if(i!=j){
                drum[i][j]=1000000;
            }
            else
            drum[i][j]=0;
        }
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(drum[i][k]+drum[k][j]<drum[i][j]){
                    drum[i][j]=drum[i][k]+drum[k][j];
                }
            }
        }
    };
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(drum[i][j]!=1000000){
                g<<drum[i][j]<<" ";
            }
            else
            g<<-1<<" ";
        }
        g<<'\n';
    }
}
int n,m,S;
int main ()
{
    ///Inceputul asta e pentru toate pana la Havel Hakimi
    /*
    f>>n>>m;
    graf G(n);
    */
    ///Rezolvare problema BFS
    //f>>S;
    //G.citire_graf_orientat(m);
    //G.BFS(S);

    ///Rezolvare problema DFS - Componente Conexe
    //G.citire_graf_neorientat(m);
    //g<<G.nr_comp_conexe();

    ///Rezolvare Sortare Topologica
    /*
    G.citire_graf_orientat(m);
    G.sortare_topologica();
    */
    ///Rezolvare Componente Tare Conexe
    /*
    G.citire_graf_orientat(m);
    G.ctc();
    */
    ///Rezolvare Componente Biconexe
    /*
    G.citire_graf_neorientat(m);
    G.Componente_Biconexe();
    */
    ///Rezolvare Muchii Critice
    /*
    G.citire_graf_neorientat(m);
    G.Muchii_Critice();
    */
    ///Rezolvare Havel Hakimi
    /*
    vector <int> grade;
    cin>>n;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        grade.push_back(x);
    }
    cout<<Havel_Hakimi(grade);
    */
    ///Rezolvare Paduri de Multimi Disjuncte
    /*
    f>>n;
    graf G(n);
    G.paduri_multimi_disjuncte();
    */
    ///Rezolvare APM cu Kruskall
    /*
    f>>n>>m;
    graf_cu_costuri G(n);
    G.citire(m);
    G.kruskall();
    */
    ///Rezolvare Dijkstra
    /*
    f>>n>>m;
    graf_cu_costuri G(n);
    G.dijkstra(m);
    */
    ///Rezolvare Bellman-Ford
    /*
    f>>n>>m;
    graf_cu_costuri G(n);
    G.bellman_ford(m);
    */
    ///Rezolvare Diametru Graf
    /*
    f>>n;
    graf G(n);
    G.citire_graf_neorientat(n-1);
    g<<G.diametru_arbore();
    */
    ///Rezolvare Floyd-Warshall
    /*
    graf_cu_matricea_ponderilor G;
    G.citire();
    G.floyd_warshall();
    */
    ///Rezolvare Flux Maxim
    f>>n>>m;
    graf G(n);
    g<<G.flux_maxim(m);
    return 0;
}