#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

const int N=;

int b[N],T,c[N],fi[N],n,t,cas,m,x,mp[N],k,a[N];

int y,z,f[N],ne[N],num,zz[N],fl[N],gp[N],dist[N],pre[N],sl[N];

void jb(int x,int y,int z,int s)

{

    ne[num]=fi[x];

    fi[x]=num;

    zz[num]=y;

    sl[num]=z;

    fl[num++]=s;

    ne[num]=fi[y];

    fi[y]=num;

    zz[num]=x;

    sl[num]=;

    fl[num++]=-s;

}

int spfa()

{

    memset(dist,0x3f,sizeof dist);

    memset(pre,-,sizeof pre);

    memset(gp,,sizeof gp);

    memset(f,,sizeof f);

    queue<int > Q;

    Q.push();

    dist[]=;

    while (!Q.empty())

     {

         int now=Q.front();

         Q.pop();

         f[now]=;

         for (int i=fi[now];i!=-;i=ne[i])

          if (sl[i]>)

           {

              int t=zz[i];

              if (dist[t]>dist[now]+fl[i])

               {

                   dist[t]=dist[now]+fl[i];

                   pre[t]=now;

                   gp[t]=i;

                   if (!f[t])

                    {

                        f[t]=;

                        Q.push(t);

                    }

               }

           }

     }

    if (pre[n+]==-)return ;

    return ;

}

void Max_flow()

{

    int cost=,flow=;

    while (!spfa())

     {

         int f=1e9;

         for (int i=n+;i>;i=pre[i])

          f=min(f,sl[gp[i]]);

         cost+=f;

        flow+=dist[n+]*f;

        for (int i=n+;i>;i=pre[i])

         {

             sl[gp[i]]-=f;

             sl[gp[i]^]+=f;

         }

     }

    printf("%d\n",-flow);

}

void init()

{

//    printf("Instance #%d: ",++cas);

    num=;

    memset(mp,,sizeof mp);

    memset(fi,-,sizeof fi);

}

void doit()

{

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

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

     {

         scanf("%d%d%d",&a[i],&b[i],&c[i]);

         f[i*-]=a[i];f[i*]=b[i];

     }

    sort(f+,f+n+n+);

    mp[f[]]=;

    int tot=;

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

     if (f[i]!=f[tot])mp[f[i]]=++tot,f[tot]=f[i];

    for (int i=;i<=tot;i++)jb(i,i+,k,);

    for (int i=;i<=n;i++)jb(mp[a[i]],mp[b[i]],,-c[i]);

    jb(,,k,);jb(tot+,tot+,k,);

    n=tot;

    Max_flow();

}

int main()

{

    scanf("%d",&T);

    while (T--)

     {

         init();

         doit();

     }

}