#include <bits/stdc++.h>
struct repRang{
    int rep;
    int rang;
};
// utila in implementarea structurii paduri de multimi disjuncte, pentru fiecare element tine minte reprezentantul si rangul

class Edge{
public:
    int i, j, cost;
    Edge(int _i, int _j, int _cost) : i(_i), j(_j), cost(_cost){}

     friend bool operator<(const Edge& e1, const Edge& e2)
    {
        return e1.cost < e2.cost;
    }
    // util in ordonarea dupa cost
};
// o structura de tip muchie, utila in problema APM cand, aplicand algoritmul lui Kruskall avem nevoie sa sortam muchiile crescator dupa cost

const int nmax = 105;
using namespace std;

int extractMin(priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& pq){
    int temp = pq.top().second;
    pq.pop();
    return temp;
}
// functie ce extrage nodul de cost minim dintre cele "nevizitate" la Dijkstra

class Graph{
   int V, E;
   vector<pair<int, int>> adj[nmax];    // lista de adiacenta ce contine perechi de tip {vecin, cost}
   bool directed, weighted;             // orientat / neorientat -- ponderat / neponderat
   static int findRep(repRang*, int);   // gaseste reprezentatul unui element in structura paduri de multimi disjuncte
   static void reunion(repRang*, int, int); // reuneste doua multimi in structura paduri de multimi disjuncte
public:
   Graph(bool, bool);
   void DF(int, bool*);                 // pentru parcurgerea in adancime, parametru int care se refera la nodul curent si vector de bool care tine minte nodurile vizitate pana acum
   void DFsol(ofstream&);               // rezolva problema DFS - componente conexe de pe infoarena
   void BFS(ofstream&, ifstream&);      // rezolva problema BFS de pe infoarena, are parametri ifstream/ofstream ca sa stie de unde citeste / unde afiseaza
   void DFbcc(int, bool*, int*, int*, ofstream&, vector<int>*, int&, stack<pair<int, int>>&); // DF - ul util in probleme componente biconexe
   void Biconexe(ofstream&);
   void DFts(int, bool*, stack<int>&);  // DFS care creeaza stiva cu nodurile in ordinea inversa a timpului de parcurgere
   void TopologicalSort(ofstream&);
   void Kosaraju(ofstream&);
   vector<pair<int, int>>* Transpose(); // construieste lista de adiacenta a grafului transpus
   void DFtranspose(vector<pair<int, int>>*, vector<int>*, int, bool*, int); // DF pentru kosaraju, luand nodurile in ordinea de pe stiva, acest DF se face pe graful transpus
   static void disjoint();
   void build(ifstream&);               // construim graful cu inputul aflat in parametrul de tip ifstream
   void Kruskal(ofstream&);
   void BellmanFord(ofstream&);
   void Dijkstra(ofstream&);
   void RoyFloyd(ifstream&, ofstream&); // deoarece inputul e prea diferit de majoritatea problemelor, fac citirea si afiseara direct in problema
   static void HavelHakimi();          // algoritmul Havel-Hakimi, determina daca o secventa de numere poate reprezenta secventa gradelor unui graf
};
Graph::Graph(bool _directed, bool _weighted) : directed(_directed), weighted(_weighted){} // constructorul, parametri se initializeaza in functie de cerinta

void Graph::DF(int src, bool* vis){
    vis[src] = true;
    for(auto ngb: adj[src]){
        if(vis[ngb.first] == false)
            {
            DF(ngb.first, vis);
            }

    }
}

void Graph::DFsol(ofstream& fout){
    int total = 0;
    bool vis[nmax] = {false};
    for(int i = 1; i <= V; ++i)
        if(vis[i] == false)
        {
            total++;
            DF(i, vis);
        }
    fout << total;
}

// la problema BFS inputul era un pic diferit asa ca nu ma mai folosesc de metoda build, fac si citirea direct in metoda
void Graph::BFS(ofstream& fout, ifstream& fin){
    int src;
    fin >> V >> E;
    fin >> src;
    for(int i = 1; i <= E; ++i)
    {
        int k, j;
        fin >> k >> j;
        adj[k].push_back(make_pair(j, 0));
    }
    queue<int> q;
    int dist[nmax];
    for(int i = 1; i <= V; ++i)
        dist[i] = - 1;
    q.push(src);
    dist[src] = 0;
    while(!(q.empty())){
        int top = q.front();
        q.pop();
        for(auto ngb : adj[top])
            if(dist[ngb.first] == - 1){
                dist[ngb.first] = dist[top] + 1;
                q.push(ngb.first);
        }
    }
    for(int i = 1; i <= V; ++i)
            fout << dist[i] << ' ';
}

// parametrii sunt: nodul curent, vectorul de vizitat, vectorul cu nivelurile nodurilor, vectorul cu nivelurile minime ale nodurilor, fisierul unde afisez, vector<int> ssol[]
// care tine minte componentele, si stiva pe care o folosesc pt a determina componentele biconexe
void Graph::DFbcc(int nod, bool* vis, int* nivel, int* nivelMin, ofstream& fout, vector<int>* ssol, int& cnt, stack<pair<int, int>>& stt){
    vis[nod] = true;
    nivelMin[nod] = nivel[nod];
    for(auto vecin: adj[nod]){
        if(vis[vecin.first] == false)
        {
            nivel[vecin.first] = nivel[nod] + 1;
            stt.push(make_pair(nod, vecin.first));
            DFbcc(vecin.first, vis, nivel, nivelMin, fout, ssol, cnt, stt);
            if(nivelMin[vecin.first] >= nivel[nod]){
                ssol[cnt].push_back(nod);
                while(!(stt.top().first == nod && stt.top().second == vecin.first))
                      {
                          ssol[cnt].push_back(stt.top().second);
                          stt.pop();
                      }
                ssol[cnt].push_back(vecin.first);
                stt.pop();
                ++cnt;
            }
                nivelMin[nod] = min(nivelMin[nod], nivelMin[vecin.first]);

        }
        else if (nivel[nod] - nivel[vecin.first] >= 2)
            nivelMin[nod] = min(nivelMin[nod], nivel[vecin.first]);

    }
}
void Graph::Biconexe(ofstream& fout){
    bool vis[nmax] = {false};
    int nivel[nmax];
    nivel[1] = 0;
    int nivelMin[nmax];
    vector<int> ssol[nmax];
    stack<pair<int, int>> stt;

    int cnt = 0;
    DFbcc(1, vis, nivel, nivelMin, fout, ssol, cnt, stt);
    fout << cnt << '\n';
    for(int i = 0; i < cnt; ++i){
        for(auto el: ssol[i])
            fout << el << ' ';
        fout << '\n';
    }
}

void Graph::DFts(int src, bool* vis, stack<int>& st){
    for(auto ngb: adj[src])
        if(vis[ngb.first] == false)
             {
                 vis[ngb.first] = true;
                 DFts(ngb.first, vis, st);
             }
    st.push(src);
}

void Graph::TopologicalSort(ofstream& fout){
    bool vis[nmax] = {false};
    stack<int> st;
    for(int i = 1; i <= V; ++i)
            if(!(vis[i]))
            {
                vis[i] = true;
                DFts(i, vis, st);
            }
    while(st.size())
        {
            fout << st.top() << ' ';
            st.pop();
        }
}

// df pe graful transpus, primeste ca parametru lista de adiacenta pt graful transpus, salveaza in sol componentele biconexe pe rand, node si visT sunt evidente, iar cnnt tine minte numarul
// componentei conexe
void Graph::DFtranspose(vector<pair<int, int>>* adjT, vector<int>* ssol, int node, bool* visT, int cnnt){
    ssol[cnnt].push_back(node);
    visT[node] = true;
    for(auto vecin: adjT[node])
            if(visT[vecin.first] == false)
            {
                DFtranspose(adjT, ssol, vecin.first, visT, cnnt);
            }
}


void Graph::Kosaraju(ofstream& fout){
        vector<pair<int, int>> adjT[nmax];
        for(int i = 1; i <= E; ++i)
            for(auto ngb : adj[i])
                adjT[ngb.first].push_back(make_pair(i, 0));
        bool visT[nmax] = {false};
        bool vis[nmax] = {false};
        stack<int> st;
        vector<int> ssol[nmax];
        for(int i = 1; i <= V; ++i)
            if(!(vis[i]))
            {
                vis[i] = true;
                DFts(i, vis, st);
            }
        int cnnt = 0;
        while(st.size())
        {
            int k = 0;
            while(st.size() && visT[st.top()] == true)
                st.pop();
            if(st.size())
                k = 1;
            if(st.size())
            {
                int crt = st.top();
                DFtranspose(adjT, ssol, crt, visT, cnnt);
            }
            if(k == 1)
                ++cnnt;
            if(st.size())
                st.pop();
        }
        fout << cnnt << '\n';
        for(int i = 0; i < cnnt; ++i)
            {
            for(auto el: ssol[i])
                fout << el << ' ';
            fout << '\n';
            }
    }

// Pentru problema disjoint, in array-ul info tinem minte pentru fiecare element reprezentantul si rangul
int Graph::findRep(repRang* info, int x){
        if(x == info[x].rep)
            return x;
        return (info[x].rep = findRep(info, info[x].rep));
}
void Graph::reunion(repRang* info, int x, int y){
        int repX = findRep(info, x);
        int repY = findRep(info, y);
        if(info[repX].rang > info[repY].rang)
            info[repX].rep = repY;
        else
            if(info[repX].rang < info[repY].rang)
                info[repY].rep = repX;
            else
                {
                    info[repX].rang++;
                    info[repY].rep = repX;
                }
}
void Graph::disjoint(){
        ifstream fin("disjoint.in");
        ofstream fout("disjoint.out");
        repRang* info = new repRang[nmax];

        int N, M;
        fin >> N >> M;
        for(int i = 1; i <= N; ++i)
            info[i].rep = i;

        for(int i = 1; i <= M; ++i){
            int cod, x, y;
            fin >> cod >> x >> y;
            if(cod == 2)
                if(findRep(info, x) == findRep(info, y))
                    fout << "DA\n";
                else
                    fout << "NU\n";
            else
                reunion(info, x, y);
        }

        delete[] info;
}
// construim graful, cu inputul venit din fisierul 'fin'
void Graph::build(ifstream& fin){
    fin >> V >> E;
    for(int i = 1; i <= E; ++i){
        int src, dest, cost;
        fin >> src >> dest;
        adj[src].push_back(make_pair(dest, 0));
        if(weighted){       // daca e ponderat, citim si costul
            fin >> cost;
            adj[src][adj[src].size() - 1].second = cost;
        }
        if(!directed)       // daca e neorientat, pentru perechea citita x y il punem pe x in lista de adiacenta a lui y si pe y in lista de adiacenta a lui x
            adj[dest].push_back(make_pair(src, 0));

    }
}
void Graph::Kruskal(ofstream& fout){
        vector<pair<int, int>> sol; // vectorul sol, unde tinem minte muchiile ce formeaza APM - ul
        repRang reps[nmax];
        vector<Edge> edges;
        for(int i = 1; i <= V; ++i)
        {
            int src = i;
            for(int j = 0; j < adj[i].size(); ++j){
                int dest = adj[i][j].first;
                int cost = adj[i][j].second;
                if(src > dest){
                    Edge temp_edge = Edge(src, dest, cost);
                    edges.push_back(temp_edge);
               }
            }
        }
        int total = 0;
        sort(edges.begin(), edges.end());
        for(int i = 1; i <= V; ++i)
        {
            reps[i].rep = i;
            reps[i].rang = 0;
        }

        int cnt = 0;
        int i = 0;
        for(;i < edges.size() && cnt <= E - 1; ++i){
            Edge temp_edge = edges[i];
            if(findRep(reps, edges[i].i) != findRep(reps, edges[i].j))
            {
                ++cnt;
                sol.push_back(make_pair(temp_edge.i, temp_edge.j));
                reunion(reps, temp_edge.i, temp_edge.j);
                total += temp_edge.cost;
            }
        }
        fout << total << '\n';
        fout << cnt << '\n';
        for(auto edg: sol){
            fout << edg.first << ' ' << edg.second << '\n';
        }
}

void Graph::BellmanFord(ofstream& fout){
    queue<int> q;
    bool inQ[nmax] = {false};
    int distMin[nmax];
    int cnt[nmax] = {0};
    distMin[1] = 0;
    for(int i = 2; i <= V; ++i)
        distMin[i] = INT_MAX / 2;
    q.push(1);
    inQ[1] = true;
    while(!(q.empty())){
        int i = q.front();
        q.pop();
        inQ[i] = false;
        for(auto ngb: adj[i]){
            int j = ngb.first;
            int cost = ngb.second;
            if(distMin[i] + cost < distMin[j]){
                distMin[j] = distMin[i] + cost;
                if(inQ[j] == false)
                    {   q.push(j);
                        inQ[j] = true;
                        ++cnt[j];
                        if(cnt[j] > V)
                            {
                                fout << "Ciclu negativ!\n";
                                return;
                            }
                    }

            }
        }
    }
    for(int i = 2; i <= V; ++i)
        fout << distMin[i] << ' ';
}

void Graph::Dijkstra(ofstream& fout){
    // min heap-ul din Dijstrka, asa se implementeaza in C++, cu parametri astia mai 'ciudati'
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    int dMin[nmax];
    dMin[1] = 0;
    for(int i = 2; i <= V; ++i)
        dMin[i] = INT_MAX / 2;
    pq.push(make_pair(0, 1));
    bool relaxedB4[nmax] = {false};

    while(!(pq.empty())){
        int crt = extractMin(pq);
        if(relaxedB4[crt] == true)
            continue;
        relaxedB4[crt] = true;
        for(auto ngb: adj[crt]){
            int vv = ngb.first;
            int ccost = ngb.second;
            if(ccost + dMin[crt] < dMin[vv])
                {
                    dMin[vv] = ccost + dMin[crt];
                    pq.push(make_pair(dMin[vv], vv));
                }
        }
    }
    for(int i = 2; i <= V; ++i)
        if(dMin[i] != INT_MAX / 2)
            fout << dMin[i] << ' ';
        else fout << 0 << ' ';
}
void Graph :: HavelHakimi(){
        vector<int> d;
        cout << "Introduceti numarul de elemente ale array-ului: ";
        int n; cin >> n;
        cout << "Introduceti elementele array-ului: ";
        int sum = 0;
        for(int i = 0; i < n; ++i){
            int temp; cin >> temp;
            d.push_back(temp);
            sum += temp;
            if(temp > n - 1)
            {
                cout << "Nu se poate construi un graf!\n";
                return;
            }
        }
        if(sum % 2)
        {
            cout << "Nu se poate construi un graf!\n";
            return;
        }

        while(d.size()){
            sort(d.begin(), d.end(), greater<int>());
            int biggest = d[0];
            d.erase(d.begin());
            for(int i = 0; i < biggest; ++i)
                {
                    --d[i];
                    if(d[i] < 0){
                        cout << "Nu se poate construi un graf!\n";
                        return;
                    }
                }
            }

        cout << "Se poate construi un graf\n";;
        return;
}

void Graph::RoyFloyd(ifstream& in, ofstream& out){
    int N;
    in >> N;
    int costMatrix[nmax][nmax]; // matricea costurilor
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            in >> costMatrix[i][j];
    for(int k = 0; k < N; ++k)
        // pana la pasul asta, am calculat distanta minima la i la j folosindu-ma de nodurile 0..k - 1 (DACA EXISTA!)
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                if(costMatrix[i][j] > costMatrix[i][k] + costMatrix[k][j] && (costMatrix[i][k] * costMatrix[k][j] != 0))
                    costMatrix[i][j] = costMatrix[i][k] + costMatrix[k][j];
    for(int i = 0; i < N; ++i)
        {
        for(int j = 0; j < N; ++j)
            out << costMatrix[i][j] << ' ';
        out << '\n';
        }
    }


int main()
{
    ifstream fin("royfloyd.in");
    ofstream fout("royfloyd.out");
    Graph g(true, true);
    g.RoyFloyd(fin, fout);
    return 0;
}