#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge{
    int v;
    int w;
};
int r[500];
int l[500];
int a[500];
int w[500];
int grap[500][500];
int cost[500][500];
vector<Edge> vec[500];
int pre[500];
int d[500];
int id[500];
int cnt;
int n,k;
int num;
void build(){
    sort(a,a+cnt);
    num=unique(a,a+cnt)-a;
    memset(grap,0,sizeof(grap));
    memset(cost,0,sizeof(cost));
    for(int i=0;i<=num+1;i++){
        vec[i].clear();
    }
    Edge temp;
    for(int i=0;i<num+1;i++){
        int u=i;
        int v=i+1;
        grap[u][v]=k;

        temp.v=v;
        temp.w=0;
        vec[u].push_back(temp);

        temp.v=u;
        vec[v].push_back(temp);
    }
    for(int i=0;i<n;i++){
        int posl=lower_bound(a,a+num,l[i])-a;
        int posr=lower_bound(a,a+num,r[i])-a;
        posl++;
        posr++;
        cost[posl][posr]=-w[i];
        grap[posl][posr]=1;

        temp.v=posr;
        temp.w=-w[i];
        vec[posl].push_back(temp);


        temp.v=posl;
        temp.w=w[i];
        vec[posr].push_back(temp);
        //printf("temp.v=%d temp.u=%d  temp.w=%d\n",posr,posl,temp.w);
    }
}
bool SPFA(){
    for(int i=0;i<=num+1;i++){
        id[i]=0;
        d[i]=0x3f3f3f3f;
        pre[i]=-1;
    }
    queue<int> q;
    q.push(0);
    id[0]++;
    d[0]=0;
    while(q.empty()==0){
        int u=q.front();
        q.pop();
        id[u]--;
        int len=vec[u].size();
        for(int i=0;i<len;i++){
            int v=vec[u][i].v;
            int w=vec[u][i].w;
            if(grap[u][v]>0&&d[u]+w<d[v]){
                d[v]=d[u]+w;
                pre[v]=u;
                if(id[v]==0){
                    id[v]++;
                    q.push(v);
                }
            }
        }
    }
    return pre[num+1]!=-1;
}
int EK(){
    int u=num+1;
    int ans=0;
    while(pre[u]!=-1){
        int v=pre[u];
        grap[v][u]--;
        grap[u][v]++;
        ans+=cost[v][u];
        u=v;
    }
    return ans;
}
int main(){
    int N;
    //freopen("test.txt","r",stdin);
    scanf("%d",&N);
    while(N--){
        scanf("%d%d",&n,&k);
        cnt=0;
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&l[i],&r[i],&w[i]);
            a[cnt++]=l[i];
            a[cnt++]=r[i];
        }
        build();
        int ans=0;
        while(SPFA()){
            ans+=EK();
        }
        printf("%d\n",-ans);
    }
    return 0;
}