#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5010;
int dp[N];
int n,k,ans,inf;
int p[N],tot;
struct Seg{int l,r,v;}s[N];
vector<int>vt;
priority_queue<int,vector<int>,greater<int> >st;
void solve()
{
cin>>n>>k;tot=ans=0;
for(int i=1;i<=n;i++)cin>>s[i].l>>s[i].r>>s[i].v,p[i]=s[i].r,ans+=s[i].v;
sort(s+1,s+n+1,[&](const Seg&x,const Seg&y){return x.r==y.r?x.l<y.l:x.r<y.r;});
p[0]=inf;sort(p+1,p+n+1);tot=unique(p+1,p+n+1)-p-1;
memset(dp,0xcf,sizeof(dp));
dp[0]=0;s[0].r=inf;
int mx=0;
// puts("----------");
for(int i=0;i<=tot;i++)
{
vt.clear();while(!st.empty())st.pop();
for(int j=1;j<=n;j++)if(s[j].l>p[i])vt.push_back(j);
int res=0;
for(int l=i+1,j=0;l<=tot;l++)
{
while(j<vt.size()&&s[vt[j]].r<=p[l])st.push(s[vt[j]].v),res+=s[vt[j]].v,j++;
while(st.size()>k)res-=st.top(),st.pop();
// cout<<i<<' '<<l<<" "<<res<<endl;
dp[l]=max(dp[l],dp[i]+res);
}
mx=max(mx,dp[i]);
}
cout<<ans-mx<<endl;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _;cin>>_;while(_--)solve();
return 0;
}
/*
2
5 1
2 6 5
4 6 2
8 8 5
1 3 4
6 8 7
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1
*/