（1）集合中元素表示（1<<i）, i从0开始

（2）注意dp[i][ss] = min(dp[i][ss], dp[i][rr | s[i]] + dp[i][(ss ^ rr) | s[i]]);，后面的要 |s[i],保证状态的正确

（3）INF初始化CLR（dp， 0x3f）

（4）注意斯坦纳树状态理解，分层松弛的理解

参考：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/

//#pragma warning (disable: 4786)

//#pragma comment (linker, "/STACK:16777216")

//HEAD

#include <cstdio>

#include <ctime>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <string>

#include <set>

#include <stack>

#include <map>

#include <cmath>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

//LOOP

#define FE(i, a, b) for(int i = (a); i <= (b); ++i)

#define FED(i, b, a) for(int i = (b); i>= (a); --i)

#define REP(i, N) for(int i = 0; i < (N); ++i)

#define CLR(A,value) memset(A,value,sizeof(A))

//INPUT

#define RI(n) scanf("%d", &n)

#define RII(n, m) scanf("%d%d", &n, &m)

#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)

#define RS(s) scanf("%s", s)

typedef long long LL;

const int INF = 0x3f3f3f3f;

const double eps = 1e-10;

const int MAXN = 1000010;

struct node{

    int to, next, l;

};

int tol;

node adj[2010];

int head[55];

void init_adj()

{

    tol = 0;

    CLR(head, -1);

}

void add_edge(int x, int y, int ll)

{

    adj[tol].to = y;

    adj[tol].l = ll;

    adj[tol].next = head[x];

    head[x] = tol++;

}

int dp[55][1 << 11];

queue<int>q;

bool inq[55][1 << 11];

int d[1 << 11];

int s[55];

int n, m, k;

int cnt, ALL;

bool check(int ss)

{

    int num = 0;

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

        if (ss & (1 << i))

            num += i < k ? 1 : -1;

    if (!num) return 1;

    return 0;

}

void spfa()

{

    while (!q.empty())

    {

        int u = q.front(); q.pop();

        int ui = u / 10000;

        int uss = u % 10000;

        inq[ui][uss] = 0;

        for (int r = head[ui]; r != -1; r = adj[r].next)

        {

            int vi = adj[r].to;

            int vss = uss | s[vi];

            if (dp[vi][vss] > dp[ui][uss] + adj[r].l)

            {

                dp[vi][vss] = dp[ui][uss] + adj[r].l;

                if (vss == uss && !inq[vi][vss]) /// 同层且不再队列中

                {

                    inq[vi][vss] = 1;

                    q.push(vi * 10000 + vss);

                }

            }

        }

    }

}

void solve()

{

    while (!q.empty()) q.pop();

    CLR(inq, 0);

    FE(ss, 0, ALL)

    {

        FE(i, 1, n)

        {

            for (int rr = ss & (ss - 1); rr; rr = (rr - 1) & ss)///ss

                    dp[i][ss] = min(dp[i][ss], dp[i][rr | s[i]] + dp[i][(ss ^ rr) | s[i]]);

            if (dp[i][ss] < INF)

                q.push(i * 10000 + ss), inq[i][ss] = 1;

        }

        spfa();

    }

    CLR(d, 0x3f);

    FE(ss, 0, ALL) FE(j, 1, n)

        d[ss] = min(d[ss], dp[j][ss]);

    REP(ss, ALL + 1)

        for(int rr = ss & (ss - 1); rr; rr = (rr - 1) & ss)

            if (check(rr) && check(ss ^ rr))

                d[ss] = min(d[ss], d[rr] + d[ss ^ rr]);

    if (d[ALL] == INF) printf("No solution\n");

    else printf("%d\n", d[ALL]);

}

void init()

{

    int x, y, l;

    init_adj();

    RIII(n, m, k);

    while (m--)

    {

        RIII(x, y, l);

        add_edge(x, y, l);

        add_edge(y, x, l);

    }

    cnt = 2 * k;

    ALL = (1 << cnt) - 1;

    CLR(s, 0);

    CLR(dp, 0x3f);

    FE(i, 1, k)///集合

    {

        s[i] = 1 << (i - 1);

        dp[i][s[i]] = 0;

        s[n - k + i] = 1 << (k + i - 1);

        dp[n - k + i][s[n - k + i]] = 0;

    }

}

int main ()

{

    int T;

    RI(T);

    while (T--)

    {

        init();

        solve();

    }

    return 0;

}