import sys

min_cost = float('inf')

line = sys.stdin.readline()
n = int(line.strip())


# Read Adjacency Matrix
# 0 indicates blocked path or same node
adj = []
for _ in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    adj.append(row)

# Precompute minimum outgoing edge for each node
# This is used for the Lower Bound calculation
min_out = []
for r in range(n):
    min_val = float('inf')
    for c in range(n):
        if r != c and adj[r][c] > 0:
            if adj[r][c] < min_val:
                min_val = adj[r][c]
    if min_val == float('inf'):
        min_val = 0 # Should ideally handle disconnected graph
    min_out.append(min_val)

visited = [False] * n
visited[0] = True
min_cost = float('inf')

def branch_and_bound(curr, count, cost):
    global min_cost

    # 1. Calculate Lower Bound
    # Lower Bound = Current Cost + Min edge leaving current + Sum of min edges leaving all unvisited
    # This estimates the best case scenario for the remaining path.
    
    remaining_bound = 0
    
    # Must leave current node
    # (We use a safe check here in case curr has no outgoing edges)
    curr_min = min_out[curr]
    remaining_bound += curr_min

    # Must leave every unvisited node
    for i in range(n):
        if not visited[i]:
            remaining_bound += min_out[i]
    
    # Pruning Step
    if cost + remaining_bound >= min_cost:
        return

    # 2. Base Case: All nodes visited
    if count == n:
        # Check if there is a path back to base (node 0)
        if adj[curr][0] > 0:
            total_cost = cost + adj[curr][0]
            if total_cost < min_cost:
                min_cost = total_cost
        return

    # 3. Branching
    for v in range(n):
        if not visited[v] and adj[curr][v] > 0:
            visited[v] = True
            branch_and_bound(v, count + 1, cost + adj[curr][v])
            visited[v] = False # Backtrack

# Start from base station (node 0)
branch_and_bound(0, 1, 0)

if min_cost == float('inf'):
    print("Path not possible")
else:
    print(f"Minimum Time: {min_cost}")


# Input 
# 4
# 0 10 15 20
# 10 0 35 25
# 15 35 0 30
# 20 25 30 0
#
# Output 
# Minimum Time: 80

# Path: 0 -> 1 -> 3 -> 2 -> 0
# Cost: 10 + 25 + 30 + 15 = 80