/*
 * Leonardo Deliyannis Constantin
 * URI 2225 - Penalização // wrong answer
*/

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 16
#define INF 0x3f3f3f3f

typedef vector<int> vi;
typedef vector<vi> vvi;

int N;
vector<vi> dist;
vector<vvi> memo;

int tsp(int u, int mask, int wps){
    if(mask == (1 << N)-1)
        return (wps > 0) ? 0 : dist[u][0];
    if(memo[u][mask][wps] != -1)
        return memo[u][mask][wps];
    int ans = INF;
    for(int v = 0; v < N; v++){
        if(v != u && !(mask & (1 << v))){
            ans = min(ans, dist[u][v] + tsp(v, mask | (1 << v), wps));
            if(wps > 0)
                ans = min(ans, tsp(v, mask | (1 << v), wps-1));
        }
    }
    return memo[u][mask][wps] = ans;
}

int main(){
    int T, M, K;
    int a, b, c, ans;
    scanf("%d", &T);
    while(T--){
        scanf("%d %d %d", &N, &M, &K);
        dist.assign(N, vi(N, INF));
        while(M--){
            scanf("%d %d %d", &a, &b, &c);
            a--; b--;
            dist[a][b] = dist[b][a] = c;
        }
        memo.assign(N, vvi(1 << N, vi(K+1, -1)));
        ans = tsp(0, 1, K);
        printf("%d\n", (ans != INF) ? ans : -1);
    }
    return 0;
}