求条，样例2输出40

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f3f3f3fll
using namespace std;
namespace __Singularity{
	ll n,a[101000],m,l,r,x,bel[101000],Fa[101000],cnt,val[101000],to[101000],ans;
	vector<pair<ll,ll> >tu[101000];
	pair<ll,pair<ll,ll> >e[101000];
	struct node{ll dis1,dis2,col1,col2;}bian[101000];
	node operator+(node p,node q){
		pair<ll,ll>a[5];
		a[1]={p.dis1,p.col1};
		a[2]={q.dis1,q.col1};
		a[3]={p.dis2,p.col2};
		a[4]={q.dis2,q.col2};
		sort(a+1,a+1+4);
		node tmp;
		tmp.dis1=a[1].first,tmp.col1=a[1].second;
		if(a[2].second!=a[1].second){
			tmp.dis2=a[2].first,tmp.col2=a[2].second;
			return tmp;
		}
		if(a[3].second!=a[1].second){
			tmp.dis2=a[3].first,tmp.col2=a[3].second;
			return tmp;
		}
		if(a[4].second!=a[1].second){
			tmp.dis2=a[4].first,tmp.col2=a[4].second;
			return tmp;
		}
		tmp.dis2=inf,tmp.col2=0;
		return tmp;
	}
	ll find(ll lx){
		if(Fa[lx]==lx) return lx;
		return Fa[lx]=find(Fa[lx]);
	}
	struct TREE{
		struct tree{node res,tag;}tr[401000];
		void build(ll pl,ll pr,ll lx){
			tr[lx].tag={inf,inf,0,0};
			if(pl==pr){
				tr[lx].res={a[pl],inf,bel[pl],0};
				return;
			}
			ll pmid=(pl+pr)>>1;
			build(pl,pmid,lx*2);
			build(pmid+1,pr,lx*2+1);
			tr[lx].res=tr[lx*2].res+tr[lx*2+1].res;
		}
		void add(ll pl,ll pr,ll lx,ll al,ll ar,node av){
			if(al<=pl&&pr<=ar){
				tr[lx].tag=tr[lx].tag+av;
				return;
			}
			tr[lx*2].tag=tr[lx*2].res+tr[lx].tag;
			tr[lx*2+1].tag=tr[lx*2+1].res+tr[lx].tag;
			ll pmid=(pl+pr)>>1;
			if(al<=pmid) add(pl,pmid,lx*2,al,ar,av);
			if(pmid<ar) add(pmid+1,pr,lx*2+1,al,ar,av);
		}
		node query(ll pl,ll pr,ll lx,ll ql,ll qr){
			if(ql<=pl&&pr<=qr) return tr[lx].res;
			ll pmid=(pl+pr)>>1;
			if(ql<=pmid&&pmid<qr) return query(pl,pmid,lx*2,ql,qr)+query(pmid+1,pr,lx*2+1,ql,qr);
			else if(ql<=pmid) return query(pl,pmid,lx*2,ql,qr);
			else return query(pmid+1,pr,lx*2+1,ql,qr);
		}
		node query(ll pl,ll pr,ll lx,ll qk){
			if(pl==pr) return tr[lx].tag;
			tr[lx*2].tag=tr[lx*2].res+tr[lx].tag;
			tr[lx*2+1].tag=tr[lx*2+1].res+tr[lx].tag;
			ll pmid=(pl+pr)>>1;
			if(qk<=pmid) return query(pl,pmid,lx*2,qk);
			else return query(pmid+1,pr,lx*2+1,qk);
		}
	}TR;
	void Main(){
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i],Fa[i]=i;
		for(int i=1;i<=m;i++) cin>>x>>l>>r,tu[x].push_back({l,r});
		while(1){
			ll fl=1;
			for(int i=1;i<=n;i++) if(find(i)!=find(1)) fl=0;
			if(fl==1) break;
			for(int i=1;i<=n;i++) bel[i]=find(i),bian[i]={inf,inf,0,0},val[i]=inf,to[i]=0;
			TR.build(1,n,1);
			cnt=0;
			for(int i=1;i<=n;i++){
				node tmp={inf,inf,0,0};
				for(auto j:tu[i]){
					tmp=tmp+TR.query(1,n,1,j.first,j.second);
					TR.add(1,n,1,j.first,j.second,{a[i],inf,bel[i],0});
				}
				if(tmp.col1!=bel[i]&&tmp.col1!=0)
					if(val[bel[i]]>tmp.dis1+a[i])
						val[bel[i]]=tmp.dis1+a[i],to[bel[i]]=tmp.col1;
				if(tmp.col2!=bel[i]&&tmp.col2!=0)
					if(val[bel[i]]>tmp.dis2+a[i])
						val[bel[i]]=tmp.dis2+a[i],to[bel[i]]=tmp.col2;
			}
			for(int i=1;i<=n;i++){
				node tmp=TR.query(1,n,1,i);
				tmp.dis1+=a[i],tmp.dis2+=a[i];
				bian[bel[i]]=bian[bel[i]]+tmp;
			}
			for(int i=1;i<=n;i++)
				if(find(i)==i){
					if(bian[i].col1!=i&&bian[i].col1!=0)
						if(val[i]>bian[i].dis1)
							val[i]=bian[i].dis1,to[i]=bian[i].col1;
					if(bian[i].col2!=i&&bian[i].col2!=0)
						if(val[i]>bian[i].dis2)
							val[i]=bian[i].dis2,to[i]=bian[i].col2;
					e[++cnt]={val[i],{i,to[i]}};
				}
			sort(e+1,e+cnt+1);
			for(int i=1;i<=cnt;i++){
				ll fu=find(e[i].second.first),fv=find(e[i].second.second);
				if(fu!=fv) Fa[fu]=fv,ans+=e[i].first;
			}
		}
		cout<<ans;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll T=1;
//	cin>>T;
	while(T--) __Singularity::Main();
	return 0;
}