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 #define maxn 55
 22 #define maxm 2500
 23 const int inf = 1 << 20;
 24 int eh[maxn], tot;
 25 int n, m, k;
 26 struct Edge {
 27     int u, v, w, next;
 28 }et[maxm];
 29 int dp[maxn][1<<10];
 30 bool visit[maxn][1<<10];
 31 int hash[maxn];
 32 int minn[1<<10];
 33 void init() {
 34     tot = 0;
 35     memset(eh, -1, sizeof(eh));
 36 }
 37 
 38 void addedge(int u, int v, int w) {
 39     Edge e = {u, v, w, eh[u]};
 40     et[tot] = e;
 41     eh[u] = tot++;
 42 }
 43 
 44 bool check(int mask) {//判断合法状态
 45     int a = 0, b = 0;
 46     for(int i = 0; i < k; i++)
 47         if(mask & (1<<i)) a++;
 48     for(int i = k; i < 2 * k; i++) 
 49         if(mask & (1<<i)) b++;
 50     return a == b;
 51 }
 52 
 53 void solve() {
 54 
 55     memset(visit, false, sizeof(visit));
 56     int base = 10000, nn = 1<<(2*k);
 57     queue<int> que;
 58 
 59     for(int i = 0; i <= n; i++) {
 60         hash[i] = 0;
 61         for(int j = 0; j < nn; j++)
 62             dp[i][j] = inf;
 63     }
 64 
 65     for(int i = 1; i <= k; i++) {
 66         hash[i] = 1<<(i-1);
 67         dp[i][hash[i]] = 0;
 68         que.push(i * base + hash[i]);
 69         visit[i][hash[i]] = true;
 70     }
 71     
 72     for(int i = 0; i < k; i++) {
 73         hash[n-i] = 1<<(k+i);
 74         dp[n-i][hash[n-i]] = 0;
 75         que.push((n-i) * base + hash[n-i]);
 76         visit[n-i][hash[n-i]] = true;
 77     }
 78 
 79     while(!que.empty()) {
 80         int u = que.front();
 81         que.pop();
 82         int mask = u % base;
 83         u /= base;
 84         visit[u][mask] = false;
 85         for(int now = eh[u]; now != -1; now = et[now].next) {
 86             int v = et[now].v, w = et[now].w;
 87             int nmask = mask | hash[v];
 88             if(dp[v][nmask] > dp[u][mask] + w) {
 89                 dp[v][nmask] = dp[u][mask] + w;
 90                 if(!visit[v][nmask]) {
 91                     que.push(v * base + nmask);
 92                     visit[v][nmask] = true;
 93                 }
 94             }
 95         }
 96         int t = nn - 1 - mask;
 97         for(int i = t; i; i = (i-1) & t) {
 98             int nmask = mask | i;
 99             if(dp[u][nmask] > dp[u][mask] + dp[u][i|hash[u]]) {
100                 dp[u][nmask] = dp[u][mask] + dp[u][i|hash[u]];
101                 if(!visit[u][nmask]) {
102                     que.push(u * base + nmask);
103                     visit[u][nmask] = true;
104                 }
105             }
106         }
107     }
108     
109     for(int i = 0; i < nn; i++)
110         minn[i] = inf;
111 
112     for(int i = 1; i <= n; i++) 
113         for(int j = 0; j < nn; j++)
114             minn[j] = min(minn[j], dp[i][j]);
115     
116     for(int i = 1; i < nn; i++)
117         if(check(i))
118             for(int j = i; j; j = (j-1) & i)
119                 if(check(j)) minn[i] = min(minn[i], minn[j] + minn[i-j]);
120 
121     int ans = minn[nn-1];
122     if(ans == inf) cout << "No solution" << endl;
123     else cout << ans << endl;
124 }
125 
126 int main() {
127     int T;
128     scanf("%d", &T);
129     while(T--) {
130         scanf("%d%d%d", &n, &m, &k);
131         init();
132         for(int i = 0; i < m; i++) {
133             int u, v, w;
134             scanf("%d%d%d", &u, &v, &w);
135             addedge(u, v, w);
136             addedge(v, u, w);
137         }
138         solve();
139     }
140     return 0;
141 }
142