#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1005;
int T,n,m;
int dp[N][N];
struct node{
	int l,r,d;
}a[N];
vector<int> v;

void solve(){
	memset(dp,0,sizeof(dp));
	v.clear();v.push_back(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r>>a[i].d;
		v.push_back(a[i].l);v.push_back(a[i].r);
	}
	sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()));m=v.size()-1;
	for(int i=1;i<=n;i++){
		a[i].l=lower_bound(v.begin(),v.end(),a[i].l)-v.begin();
		a[i].r=lower_bound(v.begin(),v.end(),a[i].r)-v.begin();
	}
	for(int len=0;len<m;len++){
		for(int L=1;L+len<=m;L++){
			int R=L+len,id=-1;
			for(int i=1;i<=n;i++){
				if(L<=a[i].l&&a[i].r<=R&&(id==-1||a[i].d>a[id].d)) id=i;
			}
			if(id==-1) dp[L][R]=0;
			else{
				dp[L][R]=-1ull>>2; 
				for(int k=a[id].l;k<=a[id].r;k++){
					dp[L][R]=min(dp[L][R],dp[L][k-1]+dp[k+1][R]);
				}
				dp[L][R]+=a[id].d;
			} 
		}
	}
	cout<<dp[1][m]<<endl;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--) solve();
	return 0;
}

上面是代码