TLE 70pts求助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
#define pb push_back
#define mkp make_pair
#define fi first
#define se second

namespace acac
{
	int read()
	{
		int ans=0;
		char ch=getchar();
		while(ch<'0'||ch>'9')
		{
			ch=getchar();
		}
		while(ch>='0'&&ch<='9')
		{
			ans=ans*10+ch-'0';
			ch=getchar();
		}
		return ans;
	}

	struct edge
	{
		int to,ne;
		ll c,w;
	}e[400010];
	int H[200010];
	int cnt=1;
	
	void add(int a,int b,ll c,ll w)
	{
		e[++cnt].to=b;
		e[cnt].ne=H[a];
		H[a]=cnt;
		e[cnt].c=c;
		e[cnt].w=w;
	}
	
	void ADD(int a,int b,ll c,ll w)
	{
		// if(c<2e7)cout<<a<<' '<<b<<' '<<c<<' '<<w<<endl;
		// else cout<<a<<' '<<b<<" "<<(c/(2e7))<<"inf "<<w<<endl;;
		add(a,b,c,w),add(b,a,0,-w);
	}
	
	ll dis[1010],hyh[200010],D[1000010],T[1010],qwq[1010];
	ll ans=0;
	priority_queue<pii,vector<pii>,greater<pii> > heap;

	void spfa(int s,int t)
	{
		memset(qwq,63,sizeof(qwq));
		memset(T,0,sizeof(T));
        int l=1,r=1;
        qwq[s]=0,D[l]=s,T[s]=1;
        while(l<=r)
        {
            int u=D[l++];
            T[u]=0;
            for(int i=H[u];i;i=e[i].ne)
            {
                int v=e[i].to;
                if(!e[i].c)continue;
                
                if(qwq[v]>qwq[u]+e[i].w)
                {
                	qwq[v]=qwq[u]+e[i].w;
                	if(!T[v])D[++r]=v,T[v]=1;
				}
            }
        }
		memset(T,0,sizeof(T));
	}
	
	int dij(int s, int t) {
		memset(dis,63,sizeof(dis));
		dis[s]=0;
		heap.push(mkp(0,s));
		while (!heap.empty()) {
			pii cur = heap.top();
			heap.pop();
			int u = cur.se;
			hyh[u]=H[u];
			if (cur.fi>dis[u]) continue;
			for (int i=H[u];i;i=e[i].ne) 
			{
				int v = e[i].to;
				ll w=e[i].w+qwq[u]-qwq[v];
				if(e[i].c&&(dis[v]>dis[u]+w))
				{
					dis[v]=dis[u]+w;
					heap.push(mkp(dis[v],v));
				}
			}
		}
		return dis[t]<1e9;
	}
	
	
	
	ll dfs(int u,int t,ll fl)
	{
		if(!fl||u==t)return fl;
		ll knd=0;
		T[u]=1;
		for(int i=hyh[u];i&&fl;i=e[i].ne)
		{
			hyh[u]=i;
			int v=e[i].to;
			ll w=e[i].w+qwq[u]-qwq[v];
			if(T[v]||!e[i].c||dis[u]+w!=dis[v])continue;
			ll k=dfs(v,t,min(fl,1ll*e[i].c));
			e[i^1].c+=k,e[i].c-=k;
			knd+=k;
			fl-=k;
		}
		T[u]=0;
		return knd;
	}
	
	ll FLOW(int s,int t)
	{
		ll res=0;
		while(dij(s,t))
		{
		//	cout<<"IN\n";
			int mfy=dfs(s,t,2e7);
			for(int i=s;i<=t;i++)
			{
				if(dis[i]<1e9)qwq[i]+=dis[i];
			}
			res+=mfy;
			ans+=mfy*qwq[t];
		//	cout<<"OUT\n";
		}
		return res;
	}

	const int inf=1e7;
	ll P[10010];
	
	int main()
	{
		int n=read(),m=read(),s=0,t=n+2;
		for(int i=1;i<=n;i++)
		{
			int a=read();
			ADD(i,i+1,a,0);
		}
		for(int i=1;i<=m;i++)
		{
			int l=read(),r=read(),w=read();
			ADD(l,r+1,inf,w);
			ans-=1ll*inf*w;
			P[l]+=inf,P[r+1]-=inf;
		}
		for(int i=1;i<=n+1;i++)
		{
			if(P[i]>0)ADD(s,i,P[i],0);
			else if(P[i]<0)ADD(i,t,-P[i],0);
		}
		spfa(s,t);
		FLOW(s,t);
		cout<<-ans;
		return 0;
	}
}

int main()
{
	acac::main();
	return 0;
}