extern crate core;

use std::str::FromStr;
use std::fmt;
use std::cmp::Ordering;
use std::fmt::{Display, Error, Formatter};
use std::ops::Range;
use std::collections::{BinaryHeap};

struct Istream {
    line: Vec<String>,
    position: usize
}
type Parse<T: FromStr> = Result<T, T::Err>;
impl Istream {
    fn new() -> Istream {
        Istream {line:vec![], position: 0}
    }
    fn read_word(&mut self) -> &String {
        if self.position == self.line.len() {
            let mut line= String::new();
            std::io::stdin().read_line(&mut line).ok();
            self.line = line.split_whitespace().map(|x|x.to_string()).collect();
            self.position = 0
        }
        let result = &self.line[self.position];
        self.position += 1;
        result
    }
    fn read(&mut self) -> String {
        self.read_word().to_string()
    }
    fn get<T: FromStr>(&mut self) -> T {self.read_word().parse().ok().unwrap()}
    fn read_usize(&mut self) -> usize {self.get()}
    fn read_int(&mut self) -> i32 {self.get()}
    fn read_long(&mut self) -> i64 {self.get()}
    fn read_double(&mut self) -> f64 {self.get()}
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    }
}

macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
macro_rules! assign_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        assign_all!(iter; $($n:$t),*);
    };
    ($iter:expr; ) => {};
    ($iter:expr; $n:ident:$t:ty) => {
        let $n: $t = $iter.next().unwrap().parse().ok().unwrap();
    };
    ($iter: expr; $n:ident:$t:ty, $($m:ident:$u:ty),*) => {
        let $n: $t = $iter.next().unwrap().parse().ok().unwrap();
        assign_all!($iter; $($m:$u),*);
    };
}
macro_rules! repeat {
    ($count:expr; $($statement:tt)+) => {
        for _ in 0 .. $count {
            $($statement)*
        }
    };
}

macro_rules! yields {
    ($count:expr; $block:block) => {{
        let mut vec = Vec::with_capacity($count);
        for _ in 0 .. $count {
            vec.push($block);
        }
        vec
    }}
}
macro_rules! array {
    ($factor: expr, ) => {$factor};
    ($factor: expr, $dimension: expr) => {{
        let size = $dimension;
        let mut vec = Vec::with_capacity(size);
        for _ in 0 .. size {
            vec.push(array!($factor, ))
        }
        vec
    }};
    ($factor:expr, $dimension:expr, $($r:expr),*) => {{
        let size = $dimension;
        let mut vec = Vec::with_capacity(size);
        for _ in 0 .. size{
            let factor = array!($factor, $($r),*);
            vec.push(factor)
        }
        vec
    }};
}
fn tabulate<F, R>(count: usize, mut generator: F) -> Vec<R> where F : FnMut(usize) -> R {
    let mut result = Vec::<R>::with_capacity(count);
    for f in 0 .. count {
        result.push(generator(f));
    }
    result
}

struct KeyValue<K, V> {
    key: K,
    value: V,
}
impl<K, V> KeyValue<K, V> {
    fn new(key: K, value: V) -> KeyValue<K, V> {
        KeyValue{key: key, value: value}
    }
}
impl<K, V> Ord for KeyValue<K, V> where K: Ord{
    fn cmp(&self, other: &Self) -> Ordering {
        other.key.cmp(&self.key)
    }
}
impl<K, V> PartialOrd for KeyValue<K, V> where K: PartialOrd {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.key.partial_cmp(&self.key)
    }
}
impl<K, V> PartialEq for KeyValue<K, V> where K: PartialEq{
    fn eq(&self, other: &Self) -> bool {
        other.key.eq(&self.key)
    }
}
impl<K, V> Eq for KeyValue<K, V> where K: Eq {}
fn main() {
    loop {
        let_all!(n: usize);
        if n == 0{
            break
        }
        let times: Vec<Vec<i32>> = tabulate(n, |_i|{
            read_line!(' ').into_iter().map(|x|x.parse::<i32>().ok().unwrap()).collect::<Vec<_>>()
        });
        let mut min_time: Vec<Vec<i32>> = array![std::i32::MAX, n, 1 << n];
        min_time[0][0] = 0;
        let mut queue = BinaryHeap::new();
        queue.push(KeyValue::new(0, (0, 0)));
        while !queue.is_empty() {
            let KeyValue{key: time, value:(current, state)} = queue.pop().unwrap();
            if state + 1 == 1 << n {
                break
            }
            if min_time[current][state] == time {
                for next in 0 .. n {
                    let mut min = times[next][0];
                    for item in 0 .. n {
                        if state & (1 << item) != 0 && min > times[next][item + 1] {
                            min = times[next][item + 1];
                        }
                    }
                    if min_time[next][state | (1 << next)] > time + min {
                        min_time[next][state | (1 << next)] = time + min;
                        queue.push(KeyValue::new(time + min, (next, state | (1 << next))))
                    }
                }
            }
        }
        println!("{}", min_time.iter().map(|a|{a.last()}).min().unwrap().unwrap())
    }
}


Measured memory_bytes: 15080