import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 외판원 순회 - 완전 탐색 알고리즘
 */
public class Main {
    static int N;
    static int[][] weight; // 각 도시로 가는 가중치 weight[a][b] -> a도시에서 b도시로 가는 비용
    static int answer = Integer.MAX_VALUE; // 최소 거리를 구하기 위해 INF 세팅

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        weight = new int[N][N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                weight[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 모든 경로를 재귀적으로 탐색하기 위해 dfs 로직 호출
        dfs(0, 0, 1);

        System.out.println(answer);
    }

    /**
     * currentCity - 현재 도착해있는 도시
     * cost - 지금까지 지나온 도시들의 가중치 합
     * visited - 지금까지 지나온 도시의 비트마스킹
     */
    private static void dfs(int currentCity, int cost, int visited) {
        // Base Case
        if (visited == ((1 << N) - 1)) { // 모든 도시를 지나쳐 왔고
            if (weight[currentCity][0] > 0) { // 다시 시작지점으로 돌아갈 수 있다면
                answer = Math.min(answer, cost + weight[currentCity][0]); // 더 작은 cost로 업데이트
            }
            return;
        }

        // Recursive Case
        for (int nextCity = 0; nextCity < N; nextCity++) { // 다음 탐색할 모든 도시 중
            if (nextCity == currentCity) continue; // (다음 탐색할 도시 == 현재 도시)면 패스
            if ((visited & (1 << nextCity)) > 0) continue; // 이미 탐색한 도시면 패스
            if (weight[currentCity][nextCity] == 0) continue; // 경로가 존재하지 않으면 패스

            // dfs 재귀적으로 호출
            dfs(nextCity, cost + weight[currentCity][nextCity], (visited | (1 << nextCity)));
        }
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * 외판원 순회 - 분기 한정법 알고리즘
 */
public class Main {
    static int N;
    static int[] pathOfTheLowest; // bound를 계산할 때 각 도시에서 갈 수 있는 최소 거리를 캐싱
    static int[][] weight; // 각 도시로 가는 가중치 weight[a][b] -> a도시에서 b도시로 가는 비용
    static int answer = Integer.MAX_VALUE; // 최소 거리를 구하기 위해 INF 세팅

    /**
     * 상태공간트리(State-Space Tree) 노드
     */
    static class Node implements Comparable<Node> {
        int currentCity, level, visited, bound, length;

        public Node(int currentCity, int level, int visited, int bound, int length) {
            this.currentCity = currentCity; // 현재 도시
            this.level = level; // 몇 개의 도시를 방문한 상태인지
            this.visited = visited; // 어떤 도시를 방문했는지
            this.bound = bound; // 하한 경계
            this.length = length; // 현재까지 방문한 경로
        }

        // 우선순위큐에서 낮은 경계부터 뽑기 위해 오버라이드
        @Override
        public int compareTo(Node o) {
            return Integer.compare(bound, o.bound);
        }
    }

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        weight = new int[N][N];
        pathOfTheLowest = new int[N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                weight[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 분기 한정법 로직 호출
        branchAndBound();

        System.out.println(answer);
    }

    private static void branchAndBound() {
        Queue<Node> pq = new PriorityQueue<>(); // 가장 작은 경계를 가진 노드를 호출하기 위해 우선순위큐 사용

        int initialBound = getInitialBound(); // 초기 최소 경계를 설정

        pq.add(new Node(0, 0, 1, initialBound, 0));

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            if (node.bound > answer) continue; // 노드의 하한이 이미 현재 정답 후보보다 크면 가망이 없으므로 패스

            int currentCity = node.currentCity;
            int visited = node.visited;
            int bound = node.bound;
            int level = node.level;
            int length = node.length;

            for (int nextCity = 0; nextCity < N; nextCity++) {
                if ((visited & (1 << nextCity)) > 0) continue; // 이미 방문한 도시면 패스
                if (weight[currentCity][nextCity] == 0) continue; // 경로가 없으면 패스

                // 다음 도시를 거쳐서, 시작점으로 돌아오면 사이클이 형성될 때는
                if (node.level == N - 2) {
                    if (weight[nextCity][0] > 0) { // 그 경로가 있다면
                        // 경로를 구하고
                        int path = node.length + weight[currentCity][nextCity] + weight[nextCity][0];

                        // 업데이트
                        answer = Math.min(answer, path);
                    }

                    continue;
                }

                int newBound = getBound(currentCity, nextCity, bound); // 경계 업데이트

                Node newNode = new Node(
                        nextCity,
                        level + 1,
                        visited | (1 << nextCity),
                        newBound,
                        length + weight[currentCity][nextCity]
                );

                if (newBound < answer) { // 경계가 현재 정답보다 작을 때만
                    pq.add(newNode); // 우선순위큐에 추가
                }
            }
        }
    }

    private static int getBound(int currentCity, int nextCity, int bound) {
        return bound - pathOfTheLowest[currentCity] + weight[currentCity][nextCity];
    }

    private static int getInitialBound() {
        int bound = 0;

        for (int startCity = 0; startCity < N; startCity++) { // 각 도시에서
            int minWeight = Integer.MAX_VALUE; // 다른 도시로 가는 최솟값을 찾기 위해 INF 초기화

            // 다른 도시로 갈 때 최소 경로를 찾기
            for (int endCity = 0; endCity < N; endCity++) {
                if (startCity == endCity) continue; // 시작 도시 == 도착 도시면 패스
                minWeight = Math.min(minWeight, weight[startCity][endCity]);
            }

            pathOfTheLowest[startCity] = minWeight; // 각 도시에서 가는 최소 경로 저장
            bound += minWeight; // 최소 경로만을 더하기
        }

        return bound;
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 외판원 순회 - 동적 계획법
 */
public class Main {
    static int N;
    static int[][] weight;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        weight = new int[N][N];
        dp = new int[N][1 << N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE); // dp 배열 최댓값으로 초기화
        }

        dp[0][1] = 0; // 0번 도시에서 시작, 0번 도시를 방문 가능 상태로 설정 (초기 비용 0)

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {
                weight[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 모든 방문 상태를 탐색
        for (int visited = 1; visited < (1 << N); visited++) { // 방문 상태를 1부터 2^N - 1까지 탐색
            for (int currentCity = 0; currentCity < N; currentCity++) { // 현재 도시를 설정
                // 현재 도시가 방문할 경로 visited에 포함되어 있지 않다면 패스
                if ((visited & (1 << currentCity)) == 0) continue;

                // 다음 방문할 도시 찾기
                for (int nextCity = 0; nextCity < N; nextCity++) {
                    // 이미 방문한 도시거나, 경로가 없을 경우 패스
                    if ((visited & (1 << nextCity)) != 0 || weight[currentCity][nextCity] == 0) {
                        continue;
                    }

                    // dp값이 유효하지 않으면 패스(앞선 연산에서 경로가 없어서 업데이트가 안됐던 것)
                    if (dp[currentCity][visited] == Integer.MAX_VALUE) continue;

                    // 다음 도시를 방문한 상태의 최소 비용 업데이트
                    dp[nextCity][(visited | (1 << nextCity))] =
                            Math.min(
                                    dp[nextCity][visited | (1 << nextCity)], // 기존 값
                                    dp[currentCity][visited] + weight[currentCity][nextCity] // 현재 도시에서 다음 도시로 이동 비용 합산
                            );
                }
            }
        }

        int answer = Integer.MAX_VALUE; // 최종적으로 최소 비용을 저장할 변수

        // 모든 도시를 방문한 상태에서 시작 도시로 돌아가는 경로의 최소 비용 계산
        for (int i = 1; i < N; i++) { // 1번 도시부터 N - 1번 도시까지 확인
            // 시작 도시로 갈 수 있는 경로가 있고, 비용이 유효하다면
            if (weight[i][0] != 0 && dp[i][(1 << N) - 1] != Integer.MAX_VALUE) {
                answer = Math.min(answer, dp[i][(1 << N) - 1] + weight[i][0]); // 최소 비용 업데이트
            }
        }

        System.out.println(answer);
    }
}