#include<bits/stdc++.h>
using namespace std;
struct road{
	int v,w;
	road(){}
	road(const int &v,const int &w):v(v),w(w){}
};
vector<road> v[100005];
int dis[100005];
bool vis[100005];
int start=0,m=-1000;
void spfa(int n){
	queue<int> q;
	int ta,tb,tc;
	m=-1000;
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&ta,&tb,&tc);
		v[ta-1].emplace_back(tb,tc);
		m=max(m,tb);
	}
	for(int i=1;i<=m;i++) v[i].emplace_back(i-1,-1);
	for(int i=1;i<=m;i++) v[i-1].emplace_back(i,0);
	for(int i=1;i<=m;i++) dis[i]=-0x3fffffff;
	dis[start]=0;
	vis[start]=true;
	q.emplace(start);
	while(q.size()){
		int r=q.front();
		q.pop();
		vis[r]=false;
		for(auto i:v[r]){
			if(dis[r]+i.w>dis[i.v]){
				dis[i.v]=dis[r]+i.w;
				if(!vis[i.v]){
					vis[i.v]=true;
					q.emplace(i.v);
				}
			}
		}
	}
	return ;
}
int t;
int main(){
	scanf("%d",&t);
	while(t){
		int n;
		memset(vis,0,sizeof(vis));
		memset(dis,0,sizeof(dis));
		for(int i=1;i<=50010;i++) v[i].clear();
		scanf("%d",&n);
		spfa(n);
		printf("%d\n",dis[m]);
		if(--t) printf("\n");
	}
	return 0;
}

在线求助dalao

急