#include <cstdio>

 #include <cstring>

 #include <vector>

 #include <queue>

 #include <iostream>

 using namespace std;

 #define pii pair<int,int>

 const int MAX = <<;

 const int INF = 0x3f3f3f3f;

 int T , n , m , k;

 vector<pii> vec[];

 int dp[][MAX] , id[];

 bool inq[];

 queue<int> que;

 void init()

 {

     for(int i= ; i<=n ; i++) vec[i].clear();

     memset(dp , 0x3f , sizeof(dp));

 }

 void add_edge(int u , int v , int w)

 {

     vec[u].push_back(make_pair(v , w));

     vec[v].push_back(make_pair(u , w));

 }

 void spfa(int cur)

 {

     while(!que.empty()){

         int u = que.front();

       // cout<<"inq: "<<u<<endl;

         que.pop(); inq[u]=false;

         int l = vec[u].size();

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

             int to = vec[u][i].first;

             if(dp[to][cur] > dp[u][cur]+vec[u][i].second){

                 dp[to][cur] = dp[u][cur]+vec[u][i].second;

                 if(!inq[to]){

                     inq[to] = true;

                     que.push(to);

                 }

             }

         }

     }

 }

 void get_id()

 {

     memset(id ,  , sizeof(id));

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

         id[i] = i , dp[i][<<(id[i]-)] = ;

         que.push(i);

         spfa(<<(id[i]-));

     }

     for(int i=k+ , j=n; i<=*k ; i++ , j--){

         id[j] = i , dp[j][<<(id[j]-)] = ;

         que.push(j);

         spfa(<<(id[j]-));

     }

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

 }

 void read_edge()

 {

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

         int u , v , w;

         scanf("%d%d%d" , &u , &v , &w);

         add_edge(u , v , w);

     }

 }

 void solve()

 {

     int all = <<(*k);

     for(int cur= ; cur<all ; cur++){

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

             for(int p=cur&(cur-) ; p ; p=(p-)&cur){

                 if(dp[i][cur] > dp[i][p]+dp[i][cur-p]){

                     dp[i][cur] = dp[i][p]+dp[i][cur-p];

                     if(!inq[i]){

                         que.push(i);

                         inq[i]=true;

                     }

                 }

             }

         }

         spfa(cur);

     }

 }

 //求出得到的子树的最小代价

 int tree[MAX] , ok[MAX] , tot , ret; //ok[]记录那些合法的状态，也就是左半部分的1等于右半部分的1

 bool is_ok(int x)

 {

     int cnt = ;

     for(int i= ; i<k ; i++) if(x&(<<i)) cnt++;

     for(int i=k ; i<*k ; i++) if(x&(<<i)) cnt--;

     return cnt == ;

 }

 void get_tree()

 {

     int all = <<(*k);

     tot = ;

     for(int cur= ; cur<all ; cur++){

         tree[cur] = INF;

         for(int i= ; i<=n ; i++) tree[cur] = min(tree[cur] , dp[i][cur]);

         if(cur> && is_ok(cur)){

             ok[++tot] = cur;

            // cout<<tot<<" "<<cur<<" "<<tree[cur]<<endl;

         }

     }

 }

 void dfs(int p , int cur , int cost , int all)

 {

     if(cost>ret) return;

     if(cur == all){

         ret = min(ret , cost);

         return;

     }

     if(p>tot) return;

     if(!(cur&ok[p])) dfs(p+ , cur|ok[p] , cost+tree[ok[p]] , all);

     dfs(p+ , cur , cost , all);

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     scanf("%d" , &T);

     while(T--)

     {

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

         init();

         read_edge();

         get_id();

         solve();

         get_tree();

         ret = INF;

         dfs( ,  ,  , (<<(*k))-);

         if(ret<INF) printf("%d\n" , ret);

         else puts("No solution");

     }

     return ;

 }