#include<bits/stdc++.h>

#define N 6003

#define inf 1000000000

using namespace std;

int n, m, k, tot;

int point[N], next1[N], v[N], len[N];

int f[][( << )], mi[], can[N], dp[( << )];

queue<int> p;

void add(int x, int y, int z) {

        tot++;

        next1[tot] = point[x];

        point[x] = tot;

        v[tot] = y;

        len[tot] = z;

        tot++;

        next1[tot] = point[y];

        point[y] = tot;

        v[tot] = x;

        len[tot] = z;

}

void spfa(int sta) {

        while (!p.empty()) {

                int now = p.front();

                p.pop();

                for (int i = point[now]; i; i = next1[i]) {

                        if (f[v[i]][sta] > f[now][sta] + len[i]) {

                                f[v[i]][sta] = f[now][sta] + len[i];

                                if (!can[v[i]]) {

                                        can[v[i]] = ;

                                        p.push(v[i]);

                                }

                        }

                }

                can[now] = ;

        }

}

bool check(int sta) { //判断当前的状态是否满足一一对应关系

        int ans = ;

        for (int i = ; i < k; i++) {

                if (sta & ( << i))

                        ans++;

                if (sta & ( << (i + k)))

                        ans--;

        }

        return (ans == );

}

int main() {

        int t;

        scanf("%d", &t);

        mi[] = ;

        for (int i = ; i <= ; i++)

                mi[i] = mi[i - ] * ;

        for (int T = ; T <= t; T++) {

                scanf("%d%d%d", &n, &m, &k);

                tot = ;

                memset(point, , sizeof(point));

                memset(next1, , sizeof(next1));

                for (int i = ; i <= m; i++) {

                        int x, y, z;

                        scanf("%d%d%d", &x, &y, &z);

                        add(x, y, z);

                }

                for (int i = ; i <= n; i++)

                        for (int j = ; j < mi[]; j++)

                                f[i][j] = inf;

                for (int i = ; i <= k; i++)

                        f[i][mi[i - ]] = ;

                int t = k;

                for (int i = n - k + ; i <= n; i++)

                        f[i][mi[t]] = , t++;

                for (int sta = ; sta < mi[t]; sta++) {

                        for (int i = ; i <= n; i++) {

                                for (int s = sta & (sta - ); s; s = sta & (s - )) {

                                        int t = f[i][sta - s] + f[i][s];

                                        f[i][sta] = min(f[i][sta], t);

                                }

                                if (f[i][sta] != inf)

                                        p.push(i), can[i] = ;

                        }

                        spfa(sta);

                }

                for (int sta = ; sta < mi[t]; sta++) {

                        dp[sta] = inf;

                        for (int i = ; i <= n; i++)

                        dp[sta] = min(dp[sta], f[i][sta]);

                }

                for (int sta = ; sta < mi[t]; sta++)

                        if (check(sta))

                                for (int s = sta & (sta - ); s; s = sta & (s - ))

                                        if (check(s))

                                                dp[sta] = min(dp[sta], dp[s] + dp[sta - s]);

                if (dp[mi[t] - ] == inf)

                        printf("No solution\n");

                else

                        printf("%d\n", dp[mi[t] - ]);

        }

}