Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

In an undirected weighted graph, we define an $s - t$ *mincut cost* as the minimum sum of weights of edges which have to be removed from the graph so that there would be no path between vertices $s$ and $t$. 

You are given a two-dimensional array $A$ with size $N \times N$. You are allowed to increase the value of each element of this array by any non-negative integer (these integers may be different for different elements). Afterwards, the array $A$ should satisfy the following condition: there is a graph $G$ with $N$ vertices (numbered $1$ through $N$) such that for each $i$ and $j$ ($1 ≤ i, j ≤ N$), the $i-j$ mincut cost in $G$ is equal to $A_{ij}$.

Let's define the *cost* of the above operation as the sum of all integers added to elements of the initial array $A$. Compute the minimum possible cost.

Note that: We consider only non-negative weight graphs.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains $N$ space-separated integers $A_{i1}, A_{i2}, \dots, A_{iN}$.

------  Output ------
For each test case, print a single line containing one integer — the minimum cost.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1,000$
$0 ≤ A_{ij} ≤ 10^{9}$ for each valid $i, j$
$A_{ii} = 0$ for each valid $i$
the sum of $N$ over all test cases does not exceed $2,000$

------  Subtasks ------
Subtask #1 (10 points): $A_{ij} ≤ 1$ for each valid $i, j$

Subtask #2 (40 points): $N ≤ 100$

Subtask #3 (50 points): original constraints

----- Sample Input 1 ------ 
3
2
0 0
1 0
3
0 0 3
1 0 1
2 0 0
4
0 0 2 2
1 0 2 0
0 3 0 3
2 4 0 0
----- Sample Output 1 ------ 
1
3
13
----- explanation 1 ------ 
Example case 1: Of course, we must increase $A_{12}$ by $1$, since $A_{21} = 1$. This is sufficient; one possible graph $G$ is shown in the picture below. (Disconnecting vertices $1$ and $2$ costs $1$.)

Example case 2: Similarly, we must increase $A_{12}$ by $1$, $A_{31}$ by $1$ and $A_{32}$ also by $1$. This is again sufficient and a possible graph $G$ is shown in the picture below. (Disconnecting vertices $1$ and $2$ costs $1$, disconnecting vertices $1, 3$ costs $3$ and disconnecting $2, 3$ costs $1$.)

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Tree algorithms

Flows and cuts

Spanning trees

Starter code:

Solutions:
inf = 100000000000
t = int(input())

def cal(i, tr, ght, vis, st, mn):
	if vis[i] == 0:
		rtv = 0
		vis[i] = 1
		for j in tr[i]:
			if vis[j] == 0:
				rtv += cal(j, tr, ght, vis, st, min(mn, ght[i][j]))
		if i != st:
			rtv += mn
		return rtv
for rr in range(t):
	n = int(input())
	g = []
	s1 = 0
	for i in range(n):
		ip = list(map(int, input().strip().split(' ')))
		g.append(ip)
	for i in range(n):
		for j in range(n):
			s1 += g[i][j]
	for i in range(n):
		for j in range(n):
			tm = max(g[i][j], g[j][i])
			g[i][j] = tm
			g[j][i] = tm
	edj = []
	for i in range(n):
		for j in range(i + 1, n):
			if g[i][j] != 0:
				edj.append([i, j, g[i][j]])
	edj = sorted(edj, key=lambda x: x[2], reverse=True)
	edgcnt = 0
	dsu = [i for i in range(n)]
	ght = [[0] * n for i in range(n)]
	tr = [[] for i in range(n)]
	while edgcnt < n - 1:
		tm = edj[0]
		i = tm[0]
		j = tm[1]
		if dsu[i] != dsu[j]:
			mn = min(dsu[i], dsu[j])
			mx = max(dsu[i], dsu[j])
			for x in range(n):
				if dsu[x] == mx:
					dsu[x] = mn
			ght[i][j] = tm[2]
			ght[j][i] = tm[2]
			tr[i].append(j)
			tr[j].append(i)
			edgcnt += 1
		edj.remove(tm)
		if len(edj) == 0:
			break
	s2 = 0
	for i in range(n):
		vis = [0] * n
		s2 += cal(i, tr, ght, vis, i, inf)
	print(s2 - s1)


T = int(input())

def root(x):
	if p[x] == x:
		return x
	p[x] = y = root(p[x])
	return y

def unite(x, y):
	px = p[x]
	py = p[y]
	if px == py:
		return -1
	if px < py:
		p[py] = px
		return px
	else:
		p[px] = py
		return py
for _ in range(T):
	N = int(input())
	A = [list(map(int, input().split())) for i in range(N)]
	ans = 0
	Q = []
	for i in range(N):
		Ai = A[i]
		for j in range(i):
			v = max(A[i][j], A[j][i])
			ans += 2 * v - A[i][j] - A[j][i]
			A[i][j] = A[j][i] = v
			Q.append((v, i, j))
	ids = [-1] * N
	Q.sort(reverse=1)
	(*p,) = range(N)
	S = [{i} for i in range(N)]
	for (v, i, j) in Q:
		pi = root(i)
		pj = root(j)
		r = unite(i, j)
		if r == -1:
			continue
		si = S[pi]
		sj = S[pj]
		for x in si:
			for y in sj:
				ans += 2 * (v - A[x][y])
		if r == pi:
			si |= sj
			S[pj] = None
		else:
			sj |= si
			S[pi] = None
	print(ans)