#include <algorithm>
#include <iostream>
#include <vector>

int Power(int x, int n) {
  int result = 1;
  while (n > 0) {
    if (n & 1 == 1) {
      result = result * x;
    }
    x = x * x;
    n = n >> 1;
  }
  return result;
}
int ClearBit(int n, int k) { return (n & (~(1 << (k)))); }
using Patrix = std::vector<std::vector<std::pair<int, int>>>;
template <typename T>
bool allEqual(std::vector<T> const& v) {
  if (v.size() == 0) {
    return false;
  }
  return std::all_of(v.begin(), v.end(),
                     [&](T const& e) { return e == v.front(); });
}
bool Zeros(std::vector<int>& v) { return v[0] == 0 && allEqual(v); }
using Matrix = std::vector<std::vector<int>>;

class Graph {
 private:
  Matrix dp_;
  Matrix cities_;
  int size_;
  Matrix paths_;
  std::pair<int, std::pair<int, int>> FindCheapest(int i, int mask) {
    if (mask == (1 << size_) - 1) {
      return {cities_[i][0], {i, mask}};
    }
    if (dp_[mask][i] != -1) {
      return {dp_[mask][i], {i, mask}};
    }
    int res = INT32_MAX;
    for (int j = 0; j < size_; ++j) {
      if ((mask & (1 << j)) == 0) {
        res = std::min(
            res, FindCheapest(j, (mask ^ (1 << j))).first + cities_[i][j]);
      }
    }
    dp_[mask][i] = res;
    return {dp_[mask][i], {i, mask}};
  }
  std::pair<int, std::pair<int, int>> Total(int src) {
    std::pair<int, std::pair<int, int>> res;
    res = FindCheapest(src, 1);
    return res;
  }

 public:
  Graph(Matrix& matrix) {
    cities_ = matrix;
    size_ = static_cast<int>(cities_.size());
    dp_.assign(Power(2, size_), std::vector<int>(size_, -1));
    paths_.assign(size_, std::vector<int>(size_, 0));
  }
  int FindBest() {
    std::vector<int> res;
    for (int i = 0; i < size_; ++i) {
      if (Zeros(cities_[i])) {
        res.push_back(0);
        int j = 0;
        for (std::vector<int>::iterator it = paths_[i].begin();
             it != paths_[i].end(); ++it) {
          *it = j++;
        }
      } else {
        res.push_back(Total(i).first);
        auto pr = Total(i);
        int mask = pr.second.second;
        int index = pr.second.first;
        // int start = pr.second.first;  // last city
        std::vector<int> path;
        // path.push_back(start);
        // mask = ClearBit(mask, index);
        while (mask != 0) {
          for (int j = 0; j < size_; ++j) {
            if (dp_[mask][index] ==
                dp_[ClearBit(mask, index)][j] + cities_[index][j]) {
              path.push_back(j);
              index = j;
              mask = ClearBit(mask, index);
            }
          }
        }
        for (auto& vec : path) {
          std::cout << vec << " ";
        }
        std::cout << "\n";
      }
    }
    int result = *std::min_element(res.begin(), res.end());
    return result;
  }
};

void Requests() {
  int n = 0;
  std::cin >> n;
  Matrix matrix(n, std::vector<int>(n, 0));
  for (auto& vec : matrix) {
    for (auto& elem : vec) {
      std::cin >> elem;
    }
  }
  Graph graph(matrix);
  std::cout << graph.FindBest() << "\n";
}
int main() {
  Requests();
  return 0;
}