import qualified Data.Matrix as Matrix
import qualified Data.Vector as Vector
import Data.Typeable
import Debug.Trace
import qualified Data.Maybe as Maybe
import qualified Control.Monad as Monad

-- inp = Matrix.fromLists [[0, 5, 8, 10, 0, 0, 3, 6],
--                     [5, 0, 2, 0, 0, 0, 0, 1],
--                     [8, 2, 0, 4, 5, 6, 0, 7],
--                     [10, 0, 4, 0, 12, 9, 7, 0],
--                     [0, 0, 5, 12, 0, 9, 0, 12],
--                     [0, 0, 6, 9, 9, 0, 8, 0],
--                     [3, 0, 0, 7, 0, 8, 0, 2],
--                     [6, 1, 7, 0, 12, 0, 2, 0]]

parseLine :: IO [Int]
parseLine = do
    line <- getLine
    map read (words line)

consoleInput :: IO [[Int]]
consoleInput = do
    input <- getLine
    Monad.replicateM (read input :: Int) parseLine

-- parseInput :: [String] -> [[Int]]
-- parseInput =
--     map
--     (\line ->
--         map
--         read
--         (words line)
--     )

matrixShift :: Matrix.Matrix Int -> Matrix.Matrix (Maybe Int)
matrixShift mat =
    Matrix.matrix
    (Matrix.nrows mat)
    (Matrix.ncols mat)
    (\(i,j) ->
        let elem = Matrix.getElem i j mat
        in
        if elem == 0 then
            Nothing
        else
            Just elem
    )

-- matrRead :: [[ Int ]]
-- matrRead = read

main = do
    mm <- consoleInput
    let inp = Matrix.fromLists mm
    print inp
    print $ solve (matrixShift inp)



folding :: Maybe([Int], Int) -> Maybe([Int], Int) -> Maybe([Int], Int)
folding (Just sum) (Just curr) =
    if snd(sum) < snd(curr) then
        Just sum
    else
        Just curr

folding Nothing (Just curr) =
    Just curr

folding Nothing Nothing =
    Nothing

folding (Just sum) Nothing =
    Just sum

enumerate :: [Maybe Int] -> [(Int, Maybe Int)]
enumerate row =
    map (\(x, y) -> ((fromInteger x), y)) (zip [1..] row)

solve_step :: Matrix.Matrix(Maybe Int) -> [Int] -> Int -> Int -> Maybe ([Int], Int)
solve_step matr way n curr =
    if (length way) == (Matrix.ncols matr) then
        -- trace ("way: " ++ show way ++ "cur: " ++ show curr) $
        Just (way, curr)
    else
        foldl
            folding
            Nothing
            (
                map
                (\ (ind, val) ->
                    solve_step
                    matr
                    (way ++ [ind])
                    ind
                    (curr + val)
                )
                (
                    map
                    (\ (ind , Just val) ->
                        (ind, val)
                    )
                    (
                        filter
                        (\
                            (ind, val) ->
                                if (length way) == ((Matrix.nrows matr) - 1) then
                                    (ind == 1) && (Maybe.isJust val)
                                else
                                    (not $ elem ind way) && (not $ ind == 1) && (Maybe.isJust val)
                          )
                        (enumerate row)
                    )
                )
            )
        where row = Vector.toList (Matrix.getRow n matr)

solve matr = solve_step matr [] 1 0