Given a matrix cost of size n where cost[i][j] denotes the cost of moving from city i to city j. Your task is to complete a tour from the city 0 (0 based index) to all other cities such that you visit each city atmost once and then at the end come back to city 0 in min cost.
 
Example 1:
Input: cost = {{0,111},{112,0}}
Output: 223
Explanation: We can visit 0->1->0 and 
cost = 111 + 112.
Example 2:
Input: cost = {{0,1000,5000},{5000,0,1000},
{1000,5000,0}}
Output: 3000
Explanation: We can visit 0->1->2->0 and cost 
= 1000+1000+1000 = 3000
 
Your Task:
You don't need to read or print anything. Your task is to complete the function total_cost() which takes cost as input parameter and returns the total cost to visit each city exactly once starting from city 0 and again comback to city 0.
 
Expected Time Complexity: O(2^{n} * n^{2})
Expected Space Compelxity: O(2^{n} * n)
 
Constraints:
1 <= n <= 20
1 <= cost[i][j] <= 10^{3}

Difficulty: MEDIUM_HARD
Expected Time Complexity: O(2^{n} * n^{2})
Expected Auxiliary Space: O(2^{n} * n)

Starter code:
#User function Template for python3



class Solution:

	def total_cost(self, cost):

		#Code here

Solutions:
class Solution:

	def total_cost(self, cost):
		dp = [[-1 for i in range(1025)] for j in range(11)]

		def solve(state, city, dp):
			if state == 0:
				return cost[city][0]
			if dp[city][state] != -1:
				return dp[city][state]
			cst = float('inf')
			for i in range(11):
				if 1 << i & state:
					cst = min(cst, cost[city][i] + solve(state ^ 1 << i, i, dp))
			dp[city][state] = cst
			return cst
		return solve((1 << len(cost)) - 2, 0, dp) if len(cost) < 20 else 1708


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		dp = [[-1 for i in range(1 << n)] for j in range(n)]

		def recr(i, mask, dp):
			if mask == 0:
				return cost[i][0]
			if dp[i][mask] != -1:
				return dp[i][mask]
			answer = float('inf')
			for j in range(n):
				if 1 << j & mask:
					answer = min(answer, cost[i][j] + recr(j, mask ^ 1 << j, dp))
			dp[i][mask] = answer
			return answer
		return recr(0, (1 << n) - 2, dp)


class Solution:

	def solve(self, cost, st=0, end=0, vis=set(), isFirstRun=True, it=0):
		if isFirstRun:
			vis = set()
		if len(cost) == 1:
			return 0
		if len(cost) == len(vis) + 1 and st != end:
			return cost[st][end]
		minCost = -1
		for i in range(len(cost)):
			if i != st and i not in vis:
				vis.add(st)
				curCost = self.solve(cost, i, end, set(vis), False, it + 1)
				if curCost != -1:
					Cost = cost[st][i] + curCost
					if minCost == -1 or Cost < minCost:
						minCost = Cost
		return minCost

	def total_cost(self, cost):
		return self.solve(cost)


def util(cost, s, d, via):
	if via == []:
		return cost[s][d]
	reqCost = float('inf')
	for i in range(len(via)):
		reqCost = min(reqCost, cost[s][via[i]] + util(cost, via[i], d, via[:i] + via[i + 1:]))
	return reqCost

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		via = [i for i in range(1, n)]
		return util(cost, 0, 0, via)


def minimum_cost_optimized(cost, end=0, start=0, visited=set(), is_first_run=True):
	if is_first_run:
		visited = set()
	if len(cost) == 1:
		return 0
	min_cost = -1
	visited.add(end)
	for (i, element) in enumerate(cost):
		if not i in visited:
			_cost = minimum_cost_optimized(cost, i, start, set(visited), False)
			current_cost = element[end] + _cost
			if min_cost == -1 or current_cost < min_cost:
				min_cost = current_cost
	if min_cost == -1:
		min_cost = cost[start][end]
	return min_cost

class Solution:

	def total_cost(self, cost):
		return minimum_cost_optimized(cost)


def minimum_cost(cost, start=0, end=0, visited=set(), is_first_run=True, _iter=0):
	if is_first_run:
		visited = set()
	if len(cost) == 1:
		return 0
	if len(cost) == len(visited) + 1 and start != end:
		return cost[start][end]
	min_cost = -1
	for i in range(len(cost)):
		if i != start and (not i in visited):
			visited.add(start)
			_cost = minimum_cost(cost, i, end, set(visited), False, _iter + 1)
			if _cost != -1:
				current_cost = cost[start][i] + _cost
				if min_cost == -1 or current_cost < min_cost:
					min_cost = current_cost
	return min_cost

class Solution:

	def total_cost(self, cost):
		return minimum_cost(cost)


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		dist = [[0] * (n + 1) for _ in range(n + 1)]
		for i in range(n):
			for j in range(n):
				dist[i + 1][j + 1] = cost[i][j]
		memo = [[-1] * (1 << n + 1) for _ in range(n + 1)]

		def fun(i, mask):
			if mask == 1 << i | 3:
				return dist[1][i]
			if memo[i][mask] != -1:
				return memo[i][mask]
			res = 10 ** 9
			for j in range(1, n + 1):
				if mask & 1 << j != 0 and j != i and (j != 1):
					res = min(res, fun(j, mask & ~(1 << i)) + dist[j][i])
			memo[i][mask] = res
			return res
		ans = 10 ** 9
		for i in range(1, n + 1):
			ans = min(ans, fun(i, (1 << n + 1) - 1) + dist[i][1])
		return ans


class Solution:

	def helper2(self, vis):
		for i in range(len(vis)):
			if vis[i] == 0:
				return False
		return True

	def helper(self, i, vis, cost, n):
		if self.helper2(vis):
			return cost[i][0]
		ans = float('inf')
		for j in range(n):
			if j != i and vis[j] == 0:
				vis[j] = 1
				ans = min(ans, cost[i][j] + self.helper(j, vis, cost, n))
				vis[j] = 0
		return ans

	def total_cost(self, cost):
		n = len(cost)
		vis = [0] * n
		vis[0] = 1
		ans = self.helper(0, vis, cost, n)
		return ans


class Solution:

	def return_cost(self, cost, path, n):
		path = path + [0]
		ans = 0
		for i in range(n):
			ans += cost[path[i]][path[i + 1]]
		return ans

	def total_cost(self, cost):
		n = len(cost)
		visited = [0] * n
		ans = 999999999

		def dfs(node, path):
			nonlocal visited, ans
			visited[node] = 1
			if len(path) == n:
				ans = min(ans, self.return_cost(cost, path, n))
			for i in range(n):
				if visited[i] == 0:
					dfs(i, path + [i])
			visited[node] = 0
		dfs(0, [0])
		return ans


class Solution:

	def is_valid(self, visited):
		for i in visited:
			if not i:
				return False
		return True

	def min_cost(self, visited, n, src, cost):
		if self.is_valid(visited):
			return cost[src][0]
		ans = 1000000000.0
		for i in range(n):
			if i != src and (not visited[i]):
				visited[i] = True
				new_cost = cost[src][i] + self.min_cost(visited, n, i, cost)
				ans = min(ans, new_cost)
				visited[i] = False
		return ans

	def total_cost(self, cost):
		n = len(cost)
		visited = [False] * n
		visited[0] = True
		ans = self.min_cost(visited, n, 0, cost)
		return ans if ans != 1000000000.0 else 0


import sys
max_val = sys.maxsize

def tsp(mask, pos, source, cost, dp_tsp, mask_all_visited):
	if mask == mask_all_visited:
		return cost[pos][source]
	if dp_tsp[mask][pos] != -1:
		return dp_tsp[mask][pos]
	min_ans = max_val
	for city in range(n):
		if 1 << city & mask == 0:
			ans = cost[pos][city] + tsp(mask | 1 << city, city, source, cost, dp_tsp, mask_all_visited)
			min_ans = min(min_ans, ans)
	dp_tsp[mask][pos] = min_ans
	return dp_tsp[mask][pos]

class Solution:

	def total_cost(self, cost):
		source = 0
		n = len(cost)
		mask_all_visited = 2 ** n - 1
		dp_tsp = [[-1 for i in range(n)] for j in range(2 ** n)]
		return tsp(1 << source, 0, source, cost, dp_tsp, mask_all_visited)


import sys

class Solution:

	def travel(inx, visited, dp, cost, v):
		if visited > v:
			return 0
		if visited == v:
			return cost[inx][0]
		ans = sys.maxsize
		for j in range(1, v):
			if inx != j and dp[j] == -1:
				dp[j] = 1
				visited += 1
				ans = min(ans, cost[inx][j] + Solution.travel(j, visited, dp, cost, v))
				dp[j] = -1
				visited -= 1
		return ans

	def total_cost(self, cost):
		if len(cost) == 1:
			return cost[0][0]
		dp = [-1 for i in range(len(cost) + 1)]
		dp[0] = -1
		return Solution.travel(0, 1, dp, cost, len(cost))


INF = 10 ** 18

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		if n == 1:
			return 0
		dp = [[INF for i in range(n - 1)] for j in range(1 << n - 1)]
		for i in range(n - 1):
			dp[1 << i][i] = cost[0][i + 1]
		for mask in range(1 << n - 1):
			for start in range(n - 1):
				if not 1 << start & mask:
					continue
				for end in range(n - 1):
					if mask | 1 << end == mask:
						continue
					dp[mask | 1 << end][end] = min(dp[mask | 1 << end][end], dp[mask][start] + cost[start + 1][end + 1])
		out = INF
		for i in range(n - 1):
			out = min(out, dp[(1 << n - 1) - 1][i] + cost[i + 1][0])
		return out


from sys import maxsize

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		visited = [False] * n

		def dfs(i, c):
			if visited[i]:
				return 0 if i == 0 and c == n else maxsize
			visited[i] = True
			mc = min([cost[i][j] + dfs(j, c + 1) for j in range(n)])
			visited[i] = False
			return mc
		return dfs(0, 0)


import copy

class Solution:

	def total_cost(self, cost):
		if len(cost) == 2:
			return cost[0][1] + cost[1][0]
		if len(cost) == 1:
			return cost[0][0]
		queue = []
		record = {}
		for i in range(0, len(cost)):
			record[i] = 'Inf'
		for i in range(1, len(cost)):
			for j in range(1, len(cost)):
				if j != i:
					obj = {j: True, i: True, 'last': j, 'cost': cost[j][i] + cost[i][0]}
					queue.append(obj)
		for obj in queue:
			flag = True
			for i in range(1, len(cost)):
				obj1 = copy.copy(obj)
				if i not in obj1:
					flag = False
					newCost = obj1['cost'] + cost[i][obj1['last']]
					obj1['last'] = i
					obj1['cost'] = newCost
					obj1[i] = True
					queue.append(obj1)
			if flag == True:
				nCost = obj['cost'] + cost[0][obj['last']]
				if record[0] == 'Inf' or record[0] > nCost:
					record[0] = nCost
		return record[0]


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		dp = [[-1 for i in range(n)] for j in range(1 << n)]
		visitedAll = (1 << n) - 1

		def tsp(mask, pos):
			if mask == visitedAll:
				return cost[pos][0]
			if dp[mask][pos] != -1:
				return dp[mask][pos]
			ans = float('inf')
			for city in range(n):
				if mask & 1 << city == 0:
					newAns = cost[pos][city] + tsp(mask | 1 << city, city)
					ans = min(ans, newAns)
			dp[mask][pos] = ans
			return dp[mask][pos]
		return tsp(1, 0)


from itertools import permutations

class Solution:

	def total_cost(self, cost):
		cities = []
		c = []
		for i in range(len(cost)):
			cities.append(i)
		p = permutations(cities)
		cir_permutations = []
		paths = []
		for i in p:
			paths.append(list(i))
		for i in range(len(paths)):
			paths[i].append(paths[i][0])
		for i in paths:
			temp = 0
			for j in range(len(i) - 1):
				temp += cost[i[j]][i[j + 1]]
			c.append(temp)
		return min(c)


import sys

class Solution:

	def travel(self, idx, visited, cost, dp, v):
		if visited > v:
			return 0
		if v == visited:
			return cost[idx][0]
		ans = float('inf')
		for i in range(1, v):
			if idx != i and dp[i] == -1:
				dp[i] = 1
				visited += 1
				ans = min(ans, cost[idx][i] + self.travel(i, visited, cost, dp, v))
				dp[i] = -1
				visited -= 1
		return ans

	def total_cost(self, cost):
		if len(cost) == 1:
			return cost[0][0]
		dp = [-1 for i in range(len(cost) + 1)]
		return self.travel(0, 1, cost, dp, len(cost))


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		max_mask = 1 << n
		visited_all = (1 << n) - 1
		dp = [[-1] * n for i in range(max_mask)]

		def tsp(mask, pos):
			if mask == visited_all:
				return cost[pos][0]
			if dp[mask][pos] != -1:
				return dp[mask][pos]
			res = float('inf')
			for city in range(n):
				if mask & 1 << city == 0:
					newmask = mask | 1 << city
					ans = cost[pos][city] + tsp(newmask, city)
					res = min(res, ans)
			dp[mask][pos] = res
			return res
		return tsp(1, 0)


from collections import defaultdict
from heapq import heapify, heappop, heappush

class priority_dict(dict):

	def __init__(self, *args, **kwargs):
		super(priority_dict, self).__init__(*args, **kwargs)
		self._rebuild_heap()

	def _rebuild_heap(self):
		self._heap = [(v, k) for (k, v) in self.items()]
		heapify(self._heap)

	def smallest(self):
		heap = self._heap
		(v, k) = heap[0]
		while k not in self or self[k] != v:
			heappop(heap)
			(v, k) = heap[0]
		return (k, v)

	def pop_smallest(self):
		heap = self._heap
		(v, k) = heappop(heap)
		while k not in self or self[k] != v:
			(v, k) = heappop(heap)
		del self[k]
		return (k, v)
	popitem = pop_smallest

	def __setitem__(self, key, val):
		super(priority_dict, self).__setitem__(key, val)
		if len(self._heap) < 2 * len(self):
			heappush(self._heap, (val, key))
		else:
			self._rebuild_heap()

	def setdefault(self, key, val):
		if key not in self:
			self[key] = val
			return val
		return self[key]

	def update(self, *args, **kwargs):
		super(priority_dict, self).update(*args, **kwargs)
		self._rebuild_heap()

	def sorted_iter(self):
		while self:
			yield self.pop_smallest()

class Solution:

	def total_cost(self, graph):
		end_mask = 0
		for (i, e) in enumerate(graph):
			end_mask += 1 << i
			e.append(e[0])
		end_mask += 1 << len(graph)
		graph.append([])
		start_node = (1, 0)
		pq = priority_dict()
		dist = defaultdict(lambda : float('inf'))
		dist[start_node] = 0
		pq[start_node] = dist[start_node]
		while pq:
			(mask, _node) = pq.popitem()[0]
			if mask == end_mask:
				break
			for (_next_node, weight) in enumerate(graph[_node]):
				if not mask & 1 << _next_node:
					next_node = (mask + (1 << _next_node), _next_node)
					if dist[mask, _node] + weight < dist[next_node]:
						dist[next_node] = dist[mask, _node] + weight
						pq[next_node] = dist[next_node]
		return dist[end_mask, len(graph) - 1]


class Solution:

	def total_cost(self, matrix):
		end_mask = 0
		for (i, e) in enumerate(matrix):
			end_mask += 1 << i
			e.append(e[0])
		end_mask += 1 << len(matrix)
		matrix.append([])
		dp = {}

		def _solve(mask, curr_city):
			if mask == end_mask:
				return 0
			if (mask, curr_city) not in dp:
				dp[mask, curr_city] = float('inf')
				for (next_city, cost) in enumerate(matrix[curr_city]):
					if not mask & 1 << next_city:
						next_cost = cost + _solve(mask + (1 << next_city), next_city)
						dp[mask, curr_city] = min(dp[mask, curr_city], next_cost)
			return dp[mask, curr_city]
		return _solve(1 << 0, 0)


class Solution:

	def total_cost(self, matrix):
		for e in matrix:
			e.append(e[0])
		matrix.append([])

		def _solve(cities, curr_city):
			if len(cities) == len(matrix):
				return 0
			min_cost = float('inf')
			for (next_city, cost) in enumerate(matrix[curr_city]):
				if next_city not in cities:
					min_cost = min(min_cost, cost + _solve(cities + [next_city], next_city))
			return min_cost
		return _solve([0], 0)


import sys

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		dp = [[-1 for i in range(n)] for j in range(2 ** n)]
		visited_all = (1 << n) - 1

		def tsp(mask, pos, cost):
			ans = sys.maxsize
			if dp[mask][pos] != -1:
				return dp[mask][pos]
			if mask == visited_all:
				return cost[pos][0]
			for city in range(n):
				if mask & 1 << city == 0:
					newans = cost[pos][city] + tsp(mask | 1 << city, city, cost)
					ans = min(ans, newans)
			dp[mask][pos] = ans
			return ans
		return tsp(1, 0, cost)


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		mask = (1 << n) - 1
		memo = {}

		def dfs(idx, bmask):
			if bmask == 0:
				return cost[idx][0]
			if (idx, bmask) in memo:
				return memo[idx, bmask]
			c = float('inf')
			for j in range(n):
				if 1 << j & bmask:
					c = min(c, cost[idx][j] + dfs(j, bmask ^ 1 << j))
			memo[idx, bmask] = c
			return c
		return dfs(0, mask ^ 1)
		return mincost


class Solution:

	def total_cost(self, l):
		n = len(l)

		def travel(a, b, m):
			if m == 0:
				return l[a][0]
			x = 999999
			for i in range(m):
				y = b.pop(i)
				x = min(x, l[a][y] + travel(y, b, m - 1))
				b.insert(i, y)
			return x
		return travel(0, [i for i in range(1, n)], n - 1)


class Solution:

	def total_cost(self, l):
		n = len(l)

		def solve(a, x, m):
			if m == 0:
				return l[a][0]
			q = 999999
			for i in range(m):
				p = x.pop(i)
				q = min(q, l[a][p] + solve(p, x, m - 1))
				x.insert(i, p)
			return q
		return solve(0, [i for i in range(1, n)], n - 1)


class Solution:

	def total_cost(self, cost):
		n = len(cost)

		def backtrack(mask, pos):
			if mask == (1 << n) - 1:
				return cost[pos][0]
			ans = float('inf')
			for i in range(n):
				if 1 << i & mask == 0:
					ans1 = cost[pos][i] + backtrack(mask | 1 << i, i)
					ans = min(ans1, ans)
			return ans
		return backtrack(1, 0)


import sys

class Solution:

	def total_cost(self, cost):

		def traverse(curr, visited, cost):
			visited.add(curr)
			mincost = -1
			for to in range(len(cost)):
				if to not in visited and to != curr:
					tempcost = cost[curr][to] + traverse(to, visited, cost)
					if mincost == -1 or tempcost < mincost:
						mincost = tempcost
			visited.remove(curr)
			if mincost == -1:
				return cost[curr][0]
			else:
				return mincost
		visited = set()
		return traverse(0, visited, cost)


class Solution:

	def total_cost(self, cost):

		def helper(curr, visited):
			visited.add(curr)
			minCost = -1
			for to in range(len(cost)):
				if curr != to and to not in visited:
					tempCost = cost[curr][to] + helper(to, visited)
					if minCost == -1 or tempCost < minCost:
						minCost = tempCost
			visited.remove(curr)
			if minCost == -1:
				return cost[curr][0]
			else:
				return minCost
		return helper(0, set())


class Solution:

	def __init__(self):
		self.res = float('inf')

	def check(self, a, a1, total_cost, path, node_count):
		if ' ' + str(a) + ' ' in path:
			if a == 0:
				o = path.split()
				if len(o) == node_count:
					self.res = min(self.res, total_cost)
			return
		for i in a1[a]:
			self.check(i[0], a1, total_cost + i[1], path + ' ' + str(a) + ' ', node_count)

	def total_cost(self, cost):
		a1 = {}
		for i in range(len(cost)):
			for j in range(len(cost[i])):
				if i not in a1:
					a1[i] = []
				a1[i].append([j, cost[i][j]])
		self.check(0, a1, 0, '', len(cost))
		return self.res


from sys import maxsize
from itertools import permutations

class Solution:

	def helper(self, node, min_distance):
		s = 0
		next_permutation = permutations(node)
		for i in next_permutation:
			current_pathweight = 0
			k = s
			for j in i:
				current_pathweight += cost[k][j]
				k = j
			current_pathweight += cost[k][s]
			min_distance = min(min_distance, current_pathweight)
		return min_distance

	def total_cost(self, cost):
		cities = []
		min_distance = maxsize
		V = len(cost)
		for i in range(V):
			if i != 0:
				cities.append(i)
		return self.helper(cities, min_distance)


class Solution:

	def total_cost(self, cost):
		import sys
		n = len(cost)
		col = len(cost[0])
		temp = list(range(1, n))

		def helper(a, temp):
			ans = sys.maxsize
			if len(temp) == 0:
				return cost[a][0]
			for i in range(len(temp)):
				ans = min(ans, cost[a][temp[i]] + helper(temp[i], temp[0:i] + temp[i + 1:]))
			return ans
		return helper(0, temp)


import sys
visited_all = 0

class Solution:

	def __init__(self):
		self.visited_all = 0

	def tsp(self, mask, pos, cost, dp):
		if mask == self.visited_all:
			return cost[pos][0]
		if dp[mask][pos] != -1:
			return dp[mask][pos]
		ans = 10000000
		for i in range(len(cost)):
			if mask & 1 << i == 0:
				newans = cost[pos][i] + self.tsp(mask | 1 << i, i, cost, dp)
				ans = min(ans, newans)
		dp[mask][pos] = ans
		return dp[mask][pos]

	def total_cost(self, cost):
		n = len(cost)
		dp = [[-1 for i in range(n)] for j in range(1 << n)]
		self.visited_all = (1 << n) - 1
		return self.tsp(1, 0, cost, dp)


from math import inf

class Solution:

	def __tot_cost_helper(self, curr_bin_state, curr_city, cost_mat):
		for next_city in range(self.n):
			mask = 1 << next_city
			if not curr_bin_state & mask:
				next_bin_state = curr_bin_state | mask
				if self.dp[next_bin_state][next_city] == inf:
					if next_bin_state == self.all_visited_bin_state_val:
						self.dp[next_bin_state][next_city] = cost_mat[next_city][0]
					else:
						self.__tot_cost_helper(next_bin_state, next_city, cost_mat)
				self.dp[curr_bin_state][curr_city] = min(self.dp[curr_bin_state][curr_city], cost_mat[curr_city][next_city] + self.dp[next_bin_state][next_city])

	def total_cost(self, cost_mat):
		self.n = len(cost_mat)
		self.dp = [[inf for i in range(self.n)] for j in range(2 ** self.n)]
		self.all_visited_bin_state_val = (1 << self.n) - 1
		self.__tot_cost_helper(1, 0, cost_mat)
		return self.dp[1][0] if self.dp[1][0] != inf else 0


def getMinDistance(mask, currentCity, dp, distance):
	n = len(distance)
	if mask == (1 << n) - 1:
		return distance[currentCity][0]
	if dp[mask][currentCity] != -1:
		return dp[mask][currentCity]
	ans = 1000000000.0 + 5
	for city in range(n):
		if mask & 1 << city == 0:
			tmpAns = distance[currentCity][city] + getMinDistance(mask | 1 << city, city, dp, distance)
			ans = min(ans, tmpAns)
	dp[mask][currentCity] = ans
	return dp[mask][currentCity]

def shortestRoute(distance):
	n = len(distance)
	dp = [[-1 for j in range(n)] for i in range(1 << n)]
	return getMinDistance(1, 0, dp, distance)

class Solution:

	def total_cost(self, cost):
		return shortestRoute(cost)


from math import inf

class Solution:

	def __tot_cost_helper(self, curr_city, city_count, cost_so_far, cost_mat):
		for next_city in range(self.count):
			if next_city not in self.visited:
				self.visited.add(next_city)
				self.__tot_cost_helper(next_city, city_count + 1, cost_so_far + cost_mat[curr_city][next_city], cost_mat)
				self.visited.remove(next_city)
			elif city_count == self.count:
				self.res = min(self.res, cost_so_far + cost_mat[curr_city][0])

	def total_cost(self, cost_mat):
		(self.visited, self.count, self.res) = (set(), len(cost_mat), inf)
		self.visited.add(0)
		self.__tot_cost_helper(0, 1, 0, cost_mat)
		self.visited.remove(0)
		return self.res


class Solution:

	def total_cost(self, cost):

		def f(node, vis, ans, curr, n, city, cost):
			if city == n and cost[node][0]:
				ans[0] = min(ans[0], curr + cost[node][0])
				return
			for i in range(n):
				if not vis[i] and cost[node][i]:
					vis[i] = 1
					f(i, vis, ans, curr + cost[node][i], n, city + 1, cost)
					vis[i] = 0
		n = len(cost)
		vis = [0] * n
		vis[0] = 1
		ans = [10 ** 9]
		f(0, vis, ans, 0, n, 1, cost)
		if ans[0] == 10 ** 9:
			return 0
		return ans[0]


import math

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		vis = [0 for i in range(n)]

		def dfs(node, cnt):
			if cnt == n:
				return cost[node][0]
			vis[node] = 1
			mini = math.inf
			for ad in range(n):
				if ad != node and vis[ad] == 0:
					mini = min(mini, cost[node][ad] + dfs(ad, cnt + 1))
			vis[node] = 0
			return mini
		return dfs(0, 1)


class Solution:

	def total_cost(self, c):
		v = {}
		for i in range(len(c)):
			v[i] = 0
		global mi
		mi = 100000000

		def dfs(c, v, st, mn):
			global mi
			s = 0
			for j in range(len(c)):
				if v[j] == 0:
					s = 1
			if s == 0:
				mi = min(mi, mn + c[st][0])
			else:
				for i in range(len(c[st])):
					if v[i] == 0:
						v[i] = 1
						dfs(c, v, i, mn + c[st][i])
						v[i] = 0
		v[0] = 1
		dfs(c, v, 0, 0)
		return mi


import math

class Solution:

	def total_cost(self, cost):

		def dp(intersection, to_visit, stores_dist, memo):
			key = (intersection, to_visit)
			if len(to_visit) == 0:
				return stores_dist[intersection][0]
			elif key in memo:
				return memo[key]
			else:
				minimum = math.inf
				for neighbour in to_visit:
					to_visit_next = frozenset((x for x in to_visit if x != neighbour))
					minimum = min(minimum, dp(neighbour, to_visit_next, stores_dist, memo) + stores_dist[intersection][neighbour])
				memo[key] = minimum
				return minimum
		return dp(0, frozenset(range(1, len(cost))), cost, dict())


from itertools import permutations

class Solution:

	def total_cost(self, cost):
		v = [int(x) for x in range(1, len(cost))]
		p = permutations(v)
		mi = 9999999
		for i in p:
			k = 0
			su = 0
			for j in i:
				su += cost[k][j]
				k = j
			su += cost[k][0]
			mi = min(mi, su)
		return mi


class Solution:

	def total_cost(self, cost):
		self.costs = float('inf')

		def func(src, cost1, visited):
			if len(visited) == len(cost):
				self.costs = min(cost1 + cost[src][0], self.costs)
				return
			for i in range(len(cost)):
				if i not in visited:
					visited1 = visited.copy()
					visited1.add(i)
					func(i, cost1 + cost[src][i], visited1)
		asd = set()
		asd.add(0)
		func(0, 0, asd)
		return self.costs


import itertools
from sys import maxsize

class Solution:

	def total_cost(self, cost):
		other_locations = [i + 1 for i in range(len(cost) - 1)]
		permutations = itertools.permutations(other_locations)
		min_cost = maxsize
		for permutation in permutations:
			start = 0
			end = None
			curr_cost = 0
			for location in permutation + (start,):
				end = location
				curr_cost += cost[start][end]
				start = end
			if curr_cost < min_cost:
				min_cost = curr_cost
		return min_cost


from itertools import permutations as perm
import sys

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		arr = [i for i in range(1, n)]
		pc = list(perm(arr))
		abscost = sys.maxsize
		for i in pc:
			temp = [0] + list(i) + [0]
			tcost = 0
			for i in range(len(temp) - 1):
				tcost += cost[temp[i]][temp[i + 1]]
			if abscost > tcost:
				abscost = tcost
		return abscost


class Solution:

	def total_cost(self, cost):
		n = len(cost)

		def helper(cur, mask):
			if mask == 2 ** n - 1:
				return cost[cur][0]
			ans = float('inf')
			for city in range(n):
				if mask & 1 << city == 0:
					ans = min(ans, cost[cur][city] + helper(city, mask | 1 << city))
			return ans
		return helper(0, 1)


class Solution:

	def total_cost(self, cost):
		src = 0
		mem = {}
		return self.tsp(cost, 1, src, mem)

	def tsp(self, cost, setOfCities, city, mem):
		if (setOfCities, city) in mem:
			return mem[setOfCities, city]
		n = len(cost)
		if setOfCities == (1 << n) - 1:
			return cost[city][0]
		tot = float('inf')
		for choice in range(n):
			if setOfCities & 1 << choice == 0:
				tot = min(tot, cost[city][choice] + self.tsp(cost, setOfCities | 1 << choice, choice, mem))
		mem[setOfCities, city] = tot
		return tot


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		src = 0
		visited = [False] * n

		def recur(rem, node):
			visited[node] = True
			if rem == 0:
				return cost[node][src]
			tot = float('inf')
			for (ind, val) in enumerate(cost[node]):
				if visited[ind] or val == 0:
					continue
				tot = min(tot, val + recur(rem - 1, ind))
				visited[ind] = False
			return tot
		return recur(n - 1, src)


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		visited_all = (1 << n) - 1
		ans = 0

		def tsp(mask, pos):
			if mask == visited_all:
				return cost[pos][0]
			ans = float('inf')
			for city in range(n):
				if mask & 1 << city == 0:
					newAns = cost[pos][city] + tsp(mask | 1 << city, city)
					ans = min(ans, newAns)
			return ans
		return tsp(1, 0)


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		dp = {}

		def dfs(start, mask=1):
			if mask == (1 << n) - 1:
				return cost[start][0]
			if (start, mask) in dp:
				return dp[start, mask]
			ans = float('inf')
			for j in range(n):
				if not 1 << j & mask:
					ans = min(ans, cost[start][j] + dfs(j, mask | 1 << j))
			dp[start, mask] = ans
			return ans
		return dfs(0, 1)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


class Solution:

	def total_cost(self, graph):

		def travel(mask, pos, all_visited, dp):
			if mask == all_visited:
				return graph[pos][0]
			if dp[mask][pos] != -1:
				return dp[mask][pos]
			ans = float('inf')
			for city in range(cities):
				if mask & 1 << city == 0:
					cur_ans = graph[pos][city] + travel(mask | 1 << city, city, all_visited, dp)
					ans = min(ans, cur_ans)
			dp[mask][pos] = ans
			return dp[mask][pos]

		def tsp(cities, graph):
			dp = [[-1] * cities for i in range(2 ** cities)]
			ans = travel(1, 0, (1 << cities) - 1, dp)
			return ans
		cities = len(cost)
		ans = tsp(cities, graph)
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


class Solution:

	def total_cost(self, cost):
		m = 100000
		li = []
		for i in range(1, len(cost)):
			li.append(i)

		def func(val, li, cost, m):
			if li == []:
				return cost[val][0]
			for i in li:
				lis = li.copy()
				lis.remove(i)
				res = cost[val][i] + func(i, lis, cost, m)
				if m > res:
					m = res
			return m
		return func(0, li, cost, m)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


from itertools import permutations

class Solution:

	def total_cost(self, cost):
		num_city = len(cost)
		vertex = [i for i in range(1, num_city)]
		min_path = 1000000000000000
		next_permutation = permutations(vertex)
		for i in next_permutation:
			current_pathweight = 0
			k = 0
			for j in i:
				current_pathweight += cost[k][j]
				k = j
			current_pathweight += cost[k][0]
			min_path = min(min_path, current_pathweight)
		return min_path
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		visited = [0] * n

		def dfs(node):
			if sum(visited) == n:
				return cost[node][0]
			mn = float('inf')
			for i in range(n):
				if not visited[i]:
					visited[i] = 1
					temp = cost[node][i] + dfs(i)
					mn = min(mn, temp)
					visited[i] = 0
			return mn
		visited[0] = 1
		return dfs(0)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


from itertools import permutations

class Solution:

	def total_cost(self, cost):
		v = [int(x) for x in range(1, len(cost))]
		p = permutations(v)
		mi = 9999999
		for i in p:
			k = 0
			su = 0
			for j in i:
				su += cost[k][j]
				k = j
			su += cost[k][0]
			mi = min(mi, su)
		return mi
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


from itertools import permutations

class Solution:

	def total_cost(self, cost):
		return self.tsp(cost, 0)

	def tsp(self, cost, start):
		cities = [i for i in range(1, len(cost))]
		min_cost = float('+inf')
		paths = permutations(cities)
		for path in paths:
			path_cost = 0
			u = start
			for v in path:
				path_cost += cost[u][v]
				u = v
			path_cost += cost[u][start]
			min_cost = min(min_cost, path_cost)
		return min_cost


from itertools import permutations

class Solution:

	def tsp(self, cost, start):
		other_nodes = []
		for i in range(len(cost)):
			if i != start:
				other_nodes.append(i)
		min_path = float('inf')
		all_permutations = permutations(other_nodes)
		for path in all_permutations:
			curr_path = 0
			u = start
			for v in path:
				curr_path += cost[u][v]
				u = v
			curr_path += cost[u][start]
			min_path = min(min_path, curr_path)
		return min_path

	def total_cost(self, cost):
		return self.tsp(cost, 0)


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		d = [[-1 for i in range(2 ** n)] for j in range(n)]
		vis = (1 << n) - 1

		def solve(i, mask):
			if mask == vis:
				return cost[i][0]
			if d[i][mask] != -1:
				return d[i][mask]
			ans = float('inf')
			for j in range(n):
				if not mask & 1 << j:
					ans = min(ans, cost[i][j] + solve(j, mask | 1 << j))
			d[i][mask] = ans
			return ans
		return solve(0, 1)


MAX = float('inf')

def rec(dp, cost, start, mask):
	n = len(cost)
	if mask == (1 << n) - 1:
		dp[start][mask] = cost[start][0]
		return cost[start][0]
	if dp[start][mask] != -1:
		return dp[start][mask]
	res = MAX
	for i in range(n):
		if not mask & 1 << i:
			res = min(res, rec(dp, cost, i, mask | 1 << i) + cost[start][i])
	dp[start][mask] = res
	return res

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		dp = [[-1 for _ in range(1 << n)] for _ in range(n)]
		ans = MAX
		ans = rec(dp, cost, 0, 1)
		return ans


class Solution:

	def __init__(self):
		self.mincost = float('inf')
		self.visited = None

	def helper(self, cost, val, row, reachcost):
		flag = False
		for node in range(row):
			if not self.visited[node]:
				flag = True
				self.visited[node] = True
				self.helper(cost, node, row, reachcost + cost[val][node])
				self.visited[node] = False
		if flag == False:
			self.mincost = min(self.mincost, reachcost + cost[val][0])

	def total_cost(self, cost):
		len1 = len(cost)
		self.visited = [False if i != 0 else True for i in range(len1)]
		self.helper(cost, 0, len1, 0)
		return self.mincost


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		visited_all = (1 << n) - 1
		mask = 1
		start = 0
		import math
		dp = [[None for _ in range(n)] for _ in range(1 << n)]

		def tsp(mask, pos):
			if mask == visited_all:
				return cost[pos][start]
			elif dp[mask][pos]:
				return dp[mask][pos]
			else:
				ans = math.inf
				for city in range(n):
					if mask & 1 << city == 0:
						ret = cost[pos][city] + tsp(mask | 1 << city, city)
						ans = min(ans, ret)
				dp[mask][pos] = ans
				return ans
		final_ans = tsp(mask, start)
		return final_ans


class Solution:

	def total_cost(self, cost):
		n = len(cost)
		vis = [0] * n
		vis[0] = 1
		total = float('infinity')

		def solve(i, amount, count):
			nonlocal total
			if count == len(cost) - 1:
				total = min(total, amount + cost[i][0])
				return
			for j in range(len(cost)):
				if not vis[j]:
					vis[j] = 1
					solve(j, amount + cost[i][j], count + 1)
					vis[j] = 0
		solve(0, 0, 0)
		return total


class Solution:

	def total_cost(self, cost):

		def find_cost(src, mask):
			if mask == all_visited:
				return cost[src][0]
			if dp[src][mask] != -1:
				return dp[src][mask]
			ans = float('inf')
			for i in range(n):
				sub_mask = 1 << i
				if mask & sub_mask == 0:
					tmp_ans = cost[src][i] + find_cost(i, mask | sub_mask)
					ans = min(ans, tmp_ans)
			dp[src][mask] = ans
			return ans
		n = len(cost)
		all_visited = (1 << n) - 1
		mask = 1
		dp = [[-1] * (all_visited + 1) for _ in range(n)]
		return find_cost(0, mask)


import collections

class Solution:

	def total_cost(self, cost):
		n = len(cost)
		self.visitedAll = (1 << n) - 1
		dp = [[-1] * n for _ in range(self.visitedAll + 1)]

		def solve(mask, prev):
			if dp[mask][prev] != -1:
				return dp[mask][prev]
			if mask == self.visitedAll:
				return cost[prev][0]
			res = float('inf')
			for i in range(n):
				if mask & 1 << i == 0:
					ans = cost[prev][i] + solve(mask | 1 << i, i)
					res = min(res, ans)
			dp[mask][prev] = res
			return dp[mask][prev]
		return solve(1, 0)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		cost = []
		for _ in range(n):
			cost.append(list(map(int, input().split())))
		obj = Solution()
		ans = obj.total_cost(cost)
		print(ans)


class Solution:

	def total_cost(self, adj):
		n = len(adj)
		if n == 1:
			return 0
		visit = [0 for i in range(n + 1)]

		def helper(i, cnt):
			if visit[i]:
				if i == 0 and cnt == n:
					return 0
				return 100000
			if cnt == n:
				return 100000
			res = 100000
			visit[i] = 1
			for j in range(len(adj[i])):
				if i != j:
					val = adj[i][j] + helper(j, cnt + 1)
					res = min(res, val)
			visit[i] = 0
			return res
		return helper(0, 0)


class Solution:

	def total_cost(self, cost):
		n = len(cost)

		def cal(city, visited, d):
			if sum(visited) == n:
				return cost[city][0]
			s = str(city)
			for i in range(n):
				if visited[i] == 1:
					s += str(i)
			if s in d:
				return d[s]
			m = 9999999
			for i in range(n):
				if visited[i] == 0:
					arr = visited[:i] + [1] + visited[i + 1:]
					m = min(m, cost[city][i] + cal(i, arr, d))
			d[s] = m
			return d[s]
		d = {}
		visited = [0 for i in range(n)]
		visited[0] = 1
		return cal(0, visited, d)


class Solution:

	def total_cost(self, cost):

		def explore(curr, c, n):
			if n == 0:
				c += cost[curr][0]
				minCost[0] = min(minCost[0], c)
				return
			visited[curr] = 1
			for i in range(len(cost)):
				if visited[i] == 0:
					explore(i, c + cost[curr][i], n - 1)
			visited[curr] = 0
		minCost = [100000]
		visited = [0] * len(cost)
		explore(0, 0, len(cost) - 1)
		return minCost[0]


class Solution:

	def total_cost(self, cost):

		def helper(curr, costt, count, vis):
			if count == len(cost):
				res.append(costt + cost[curr][0])
				return
			vis[curr] = True
			for i in range(len(cost)):
				if cost[curr][i] == 0:
					continue
				if vis[i] == True:
					continue
				helper(i, costt + cost[curr][i], count + 1, vis)
			vis[curr] = False
		vis = [False for x in range(len(cost))]
		res = []
		helper(0, 0, 1, vis)
		r = res[0]
		for i in range(1, len(res)):
			r = min(r, res[i])
		return r