1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 
22 #define maxn 100
23 const int inf = 1 << 27;
24 int maz[maxn][maxn];
25 int n, m;
26 
27 int StoerWagner(int n) {//n 為點數(shù)
28     int v[maxn], dist[maxn];
29     bool visit[maxn];
30     int cut = inf;
31     for(int i = 0; i < n; i++) v[i] = i;
32     while(n > 1) {
33         int k = 1, pre = 0;
34         for(int i = 1; i < n; i++) {
35             dist[v[i]] = maz[v[0]][v[i]];
36             if(dist[v[i]] > dist[v[k]]) k = i;
37         }
38         memset(visit, false, sizeof(visit));
39         visit[v[0]] = true;
40         for(int i = 1; i < n; i++) {
41             if(i == n - 1) {
42                 cut = min(cut, dist[v[k]]);
43                 for(int j = 0; j < n; j++) {
44                     maz[v[pre]][v[j]] += maz[v[j]][v[k]];
45                     maz[v[j]][v[pre]] += maz[v[j]][v[k]];
46                 }
47                 v[k] = v[--n];
48             }
49             visit[v[k]] = true;
50             pre = k, k = -1;
51             for(int j = 1; j < n; j++) {
52                 if(!visit[v[j]]) {
53                     dist[v[j]] += maz[v[pre]][v[j]];
54                     if(k == -1 || dist[v[k]] < dist[v[j]])
55                         k = j;
56                 }
57             }
58         }
59     }
60     return cut;
61 }
62 
63 int main() {
64     int T;
65     while(scanf("%d", &T), T) {
66         while(T--) {
67             scanf("%d%d", &n, &m);
68             memset(maz, 0, sizeof(maz));
69             int sum = 0;
70             for(int i = 0; i < n; i++)
71                 for(int j = 0; j < n; j++) {
72                     scanf("%d", &maz[i][j]);
73                     sum += maz[i][j];
74                 }
75             int ans = sum - 4 * StoerWagner(n);
76             cout << ans << endl;
77         }
78     }
79     return 0;
80 }
81