呐，我们可以转化一下题面：

把某个正整数看作位置，选择这个正整数 即 此位置取 \(1\) ，不选表示此位置取 \(0\)

然后就得到了一个 \(01\) 串。

所以我们可以考虑维护一个前缀和，限制条件\(l-r\)至少有 \(k\) 个数即：

\[sum_r - sum_[l-1] >= k\]

但是实际上还有一个隐藏的限制条件：

\[sum_{i+1} - sum_i>=0\]

且：

\[sum_{i} - sum_{i+1}>=-1 \]

所以都要连边，然后跑最长路 \(QwQ\)

#include<bits/stdc++.h>
using namespace std;
int read() {
    char cc = getchar(); int cn = 0, flus = 1;
    while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
    while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
    return cn * flus;
}
const int N = 5e5 + 5; 
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
int n, maxn, dis[N], S, book[N], head[N], cnt, minn, vis[N];
struct E {
    int to, next, w;
} e[N * 2];
void init() {
    memset( head, 0, sizeof(head) ), cnt = 0;
}
void add( int x, int y, int z ) {
    e[++ cnt] = (E){ y, head[x], z }, head[x] = cnt;
}
void input() {
    n = read(); int x, y, z; minn = N;
    rep( i, 1, n ) {
        x = read(), y = read(), z = read(); 
        if( x > y ) swap( x, y );
        add( x - 1, y, z );
        maxn = max( maxn, y );
    }
    rep( i, 0, maxn ) add( i, i + 1, 0 ), add( i + 1, i, -1 );
}
queue< int> q;
void spfa( int x ) {
    while( !q.empty() ) q.pop();
    memset( dis, -63, sizeof(dis) ), memset( vis, 0, sizeof(vis) );
    memset( book, 0, sizeof(book) );
    dis[x] = 0, q.push(x);
    while( !q.empty() ) {
        int u = q.front(); q.pop(); 
        book[u] = 0, vis[u] = 1;
        Next( i, u ) {
            int v = e[i].to;
            if( dis[v] < dis[u] + e[i].w ) {
                if( !book[v] ) q.push(v), book[v] = 1;
                dis[v] = dis[u] + e[i].w;
            }
        }
    }
}
signed main()
{
    int T = read();
    while( T-- ) {
        init(), input();
        spfa(S), printf("%d\n", dis[maxn]);
        if(T) puts("");
    }
    return 0;
}