区间连边先想到线段树优化建图，但显然的是这样建图求 MST 根本没法做。需要另想他法。
前两天刚做了弹跳，此题并没有直接建图，而是模拟了 Dijkstra 来跑最短路。同理，此题我们也可以不直接建图，而是通过模拟 Kruskal 来求 MST。
将边按照权值从小到大排序，注意到连完边后 \([l,r]\) 的每一个点都会进入到一个连通块中，用 set 维护连通块（也就是珂朵莉树），这样连边就转化为了合并和 \([l,r]\) 有交的每一个连通块，假如第 \(i\) 次将 \(k\) 个连通块合并，那代价就是 \(c_i\times k\)。
原来 \(n\) 个点分属于 \(n\) 个连通块，最多合并 \(n-1\) 次，时间复杂度 \(O(n\log n)\)。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mkp make_pair
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=2e5+5;
int n,m;
struct node{int l,r;long long c;}q[N];
set<pii> s;
long long ans;
signed main(){
rd(n,m);
for(int i=1;i<=n;i++)s.insert({i,i});
for(int i=1;i<=m;i++)
rd(q[i].l,q[i].r,q[i].c);
sort(q+1,q+m+1,[](node a,node b){return a.c<b.c;});
for(int i=1;i<=m;i++){
auto st=--s.upper_bound({q[i].l,n}),ed=s.upper_bound({q[i].r,n});
for(auto it=st;it!=ed;it++)ans+=q[i].c;
pii nw=mkp(st->first,prev(ed)->second);
s.erase(st,ed);
s.insert(nw);
}
if(s.size()>1)printf("-1\n");
else printf("%lld\n",ans);
return 0;
}