#include<cstdio>

 #include<cstring>

 #include<queue>

 #include<algorithm>

 using namespace std;

 #define INF (1<<30)

 #define MAXN 444

 #define MAXM 444*444*2

 struct Edge{

     int u,v,cap,cost,next;

 }edge[MAXM];

 int head[MAXN];

 int NV,NE,vs,vt;

 void addEdge(int u,int v,int cap,int cost){

     edge[NE].u=u; edge[NE].v=v; edge[NE].cap=cap; edge[NE].cost=cost;

     edge[NE].next=head[u]; head[u]=NE++;

     edge[NE].u=v; edge[NE].v=u; edge[NE].cap=; edge[NE].cost=-cost;

     edge[NE].next=head[v]; head[v]=NE++;

 }

 bool vis[MAXN];

 int d[MAXN],pre[MAXN];

 bool SPFA(){

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

         vis[i]=;

         d[i]=INF;

     }

     vis[vs]=;

     d[vs]=;

     queue<int> que;

     que.push(vs);

     while(!que.empty()){

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

         for(int i=head[u]; i!=-; i=edge[i].next){

             int v=edge[i].v;

             if(edge[i].cap && d[v]>d[u]+edge[i].cost){

                 d[v]=d[u]+edge[i].cost;

                 pre[v]=i;

                 if(!vis[v]){

                     vis[v]=;

                     que.push(v);

                 }

             }

         }

         vis[u]=;

     }

     return d[vt]!=INF;

 }

 int MCMF(){

     int res=;

     while(SPFA()){

         int flow=INF,cost=;

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             flow=min(flow,edge[pre[u]].cap);

         }

         for(int u=vt; u!=vs; u=edge[pre[u]].u){

             edge[pre[u]].cap-=flow;

             edge[pre[u]^].cap+=flow;

             cost+=flow*edge[pre[u]].cost;

         }

         res+=cost;

     }

     return res;

 }

 int from[],to[],cost[];

 int point[],pn;

 int main(){

     int t,n,k;

     scanf("%d",&t);

     while(t--){

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

         pn=;

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

             scanf("%d%d%d",from+i,to+i,cost+i);

             point[pn++]=from[i]; point[pn++]=to[i];

         }

         sort(point,point+pn);

         pn=unique(point,point+pn)-point;

         vs=pn; vt=vs+; NV=vt+; NE=;

         memset(head,-,sizeof(head));

         addEdge(vs,,k,);

         addEdge(pn-,vt,k,);

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

             addEdge(i-,i,INF,);

         }

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

             int x=lower_bound(point,point+pn,from[i])-point;

             int y=lower_bound(point,point+pn,to[i])-point;

             addEdge(x,y,,-cost[i]);

         }

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

     }

     return ;

 }