#include <bits/stdc++.h>

#define NMAX 50010   // ATENTIE la cat e in problema curenta !!!
#define oo (1 << 30) // ATENTIE la cat e in problema curenta !!!
#define NO_PARENT (-1)

using namespace std;

class Task {
public:
  void solve() {
    read_input();
    print_output(get_result());
  }

private:
  // n = numar de noduri, m = numar de muchii
  int n, m;

  // Listele de adiacenta pentru fiecare nod
  //vector<pair<int, int>> adj[NMAX]; 
  int adj[NMAX][NMAX];

  // Matrice auxiliara unde se vor calcula noile costuri
  //vector<pair<int, int>> aux_adj[NMAX];

  void read_input() {
    //ifstream fin ("johnson.in"); 
    ifstream fin ("royfloyd.in");

    // CITIRE MUCHII:
    // fin >> n >> m;

    // for (int i = 1; i <= m; ++i) {
    //   // Citim m muchii de forma x -> y  cu costul c
    //   int x, y, c;
    //   fin >> x >> y >> c;

    //   // Adaugam in lista de adiacenta a nodului x
    //   // nodul y cu costul muchiei x -> y = c
    //   adj[x].push_back({y, c});
    //   aux_adj[x].push_back({y, c});
    // }

    // CITIRE ROY-FLOYD
    fin >> n;
        for (int x = 1; x <= n; ++x) {
          for (int y = 1; y <= n; ++y) {
              int c; // x -> y, of cost c
              fin >> c;
              if (c == 0) {
                  c = oo;
              }
              adj[x][y] = c;
              //p[x][y] = x;
          }
        }
    
    fin.close();
  }

  bool get_result() { return Johnson(); }

  void Dijkstra(int source, vector<int> &d) {
    // Min-heap ce contine perechi de tipul: distanta source -> x
    // Folosit pentru a extrage la fiecare pas nodul care are costul
    // estimat minim fata de sursa
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                    std::greater<pair<int, int>>> pq;
    
    // Presupunem ca nu exista drum de la source la i
    for (int i = 1; i <= n; ++i) {
      d[i] = oo;
    }

    // Initializam distanta source -> source = 0
    d[source] = 0;
    // Adaugam in heap sursa cu prioritate = cost
    pq.push({d[source], source});

    while (!pq.empty()) {
      // Extragem nodul cu costul estimat minim fata de sursa
      auto entry = pq.top();
      pq.pop();

      int cost = entry.first;
      int node = entry.second;

      // Daca intrarea curenta nu este up-to-date
      // Adica s-a modificat costul fata de cel deja existent in heap
      if (cost > d[node]) {
        continue;
      }

      // Pentru fiecare vecin incercam sa relaxam costul de la sursa
      // la el trecand prin nodul node
      //for (auto &edge : adj[node]) {
      for (int i = 1; i <= n; ++i) {  
        int neighbour = i; //edge.first;
        int cost_edge = adj[node][i]; //edge.second;

        // Daca obtinem un cost mai mic trecand prin node
        if (d[node] + cost_edge < d[neighbour]) {
          // Salvam noua distanta
          d[neighbour] = d[node] + cost_edge;

          // Actualizam costul drumului de la sursa la vecin
          pq.push({d[neighbour], neighbour});
        }
      }
    }

    // Optional: Daca nu se poate ajunge in nodul i din source
    // modificam distanta din oo intr-o valoare corespunzatoare
    // Infoarena vrea sa nu afisez oo, ci 0
    // for (int i = 1; i <= n; ++i) {
    //   if (d[i] == oo) {
    //     d[i] = -1;
    //   }
    // }
  }

   bool BellmanFord(int source, vector<int> &d) {
    // Coada folosita la algoritmul BellmanFord
    queue<int> q;

    // used[i] = de cate ori a fost folosit nodul i
    vector<int> used(n + 2, 0);

    // Presupunem ca nu exista drum de la source la i
    for (int i = 1; i <= n + 1; ++i) {
      d[i] = oo;
    }

    // Distanta source -> source = 0
    d[source] = 0;

    // Adaugam source in coada
    q.push(source);

    while (!q.empty()) {
      int node = q.front();
      q.pop();

      // Crestem numarul de utilizari al nodului node
      ++used[node];
      if (used[node] > n + 1) {
        return true; // Am gasit ciclu de cost negativ
      }

      // Pentru fiecare vecin incercam sa relaxam costul de la sursa
      // la el trecand prin nodul node
      // for (auto &edge : adj[node]) {
      //   int neighbour = edge.first;
      //   int cost_edge = edge.second;
      for (int i = 1; i <= n; ++i) {  
        int neighbour = i; //edge.first;
        int cost_edge = adj[node][i]; //edge.second;

        // Daca obtinem un cost mai mic trecand prin node
        if (d[node] + cost_edge < d[neighbour]) {

          // Salvam noua distanta
          d[neighbour] = d[node] + cost_edge;

          // Actualizam costul drumului de la sursa la vecin
          q.push(neighbour);
        }
      }
    }

    return false;
  }

    bool Johnson () {
        // Cream legaturi de la nodul nou la toate celelalte
        for (int i = 1; i <= n; ++i) {
            adj[n + 1][i] = 0; //.push_back({i, 0});
        }

        // Initializam vectorul pe care il vom trimite la BellmanFord cu valoarea oo
        vector<int> vertex_weight(n + 2, oo);

        // Aplicam BellmanFord cu noul nod ca sursa pentru a afla costurile nodurilor
        bool neg_cycle = BellmanFord (n + 1, vertex_weight);
        cout << "Computed BF\n";

        // Daca s-a gasit un ciclu negativ, oprim algoritmul
        if (neg_cycle) {
            return true;
        }

        // Aflam noile costuri ale muchiilor
        for (int i = 1; i <= n + 1; ++i) {
            //for (auto &entry : aux_adj[i]) {
            for (int j = 1; j<= n + 1; ++j) {  
                //entry.second += (vertex_weight[i] - vertex_weight[entry.first]);
                adj[i][j] += (vertex_weight[i] - vertex_weight[j]);
            }
        }
        cout << "Reweighed matrix\n";

        // Aplicam Dijkstra din fiecare nod pentru a afla distantele
        vector<int> current_dijkstra(n + 1, oo);
        for (int i = 1; i <= n; ++i) {
            Dijkstra(i, current_dijkstra);
            for (int j = 1; j <= n; ++j) {
                adj[i][j] = current_dijkstra[j];
            }
        
        }

        cout << "Computed Dijkstra\n";
        return false;
    }

  void print_output(bool negative_cycle) {
    //ofstream fout ("johnson.out");
    ofstream fout ("royfloyd.out");
    if (negative_cycle) {
        fout << "S-a gasit un ciclu negativ";
        return;
    }

    //fout << "Distantele finale sunt:\n\n";
    for (int i = 1; i <= n; ++i) {
        //fout << "Pentru nodul " << i << ": ";
        for (int j = 1; j <= n; ++j) {
            //fout << "d(" << i << ", " << adj[i][j].first << ") = " << adj[i][j].second << ", ";
            fout << adj[i][j] << " ";
        }
        fout << "\n";
        //fout << "d(" << i << ", " << adj[i][adj[i].size() - 1].first << ") = " << adj[i][adj[i].size() - 1].second << "\n";
    }

    fout.close();
  }
};

int main() {
  Task *task = new Task();
  task->solve();
  delete task;
  return 0;
}