题意
首先考虑限制：
1.每个点只能走一次。
2.每条边从编号小的走向边号大的，必定是个(DAG)。
3.我们可以随时用一定花费跳跃到另一个点上。
我们发现最后答案必定是这样的：
跳到一个点，走一段，再跳一段，再走一段，如此往复。
于是我们可以将这个过程理解为选几条路径覆盖所有点的问题。
我们将每个点拆成入点和出点。
首先套路地从每个出点向汇点连容量为(1)费用为(0)的边，这是为了保证每个点只走一次。
我们从源点向每个出点(i')连容量为(1)费用为(a_i)，表示我们开启了一个以(i)为起点的路径。
现在我们考虑对于一条边((u,v)(u<v))怎么处理：
这表示我们可以从(u)走到(v)而避免跳跃到(v)，因此我们从(u)的入点向(v)的出点连边。
最后我们从(S)向每个入点连容量为(1)费用为(0)的边，为什么接下来说：
这时我们就要用到(DAG)图的性质了，我们现在保证了每个点的出点至少有一个前继点：这个点要么是1.源点，2.要么是一个入点。
对于1.自然合法，就表示直接跳跃。
对于2.，我们发现从这个点一直回溯必定能找到一个跳跃来的点，因为这个图没有环。
code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1610;
const int maxm=15010;
const int inf=1e9;
int n,m,cnt=1,S,T;
int a[maxn],head[maxn],dis[maxn];
bool vis[maxn];
struct edge{int to,nxt,flow,cost;}e[(maxn*maxn)<<1];
inline void add(int u,int v,int w,int c)
{
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].flow=w;
e[cnt].cost=c;
}
inline void addflow(int u,int v,int w,int c){add(u,v,w,c);add(v,u,0,-c);}
inline bool spfa()
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
queue<int>q;
q.push(S);dis[S]=0;vis[S]=1;
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i;i=e[i].nxt)
{
if(e[i].flow<=0)continue;
int y=e[i].to;
if(dis[y]>dis[x]+e[i].cost)
{
dis[y]=dis[x]+e[i].cost;
if(!vis[y])q.push(y),vis[y]=1;
}
}
}
return dis[T]!=0x3f3f3f3f;
}
int dfs(int x,int lim)
{
if(lim<=0||x==T)return lim;
int res=lim;
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(e[i].flow<=0||vis[y]||dis[y]!=dis[x]+e[i].cost)continue;
int tmp=dfs(y,min(res,e[i].flow));
res-=tmp;
e[i].flow-=tmp,e[i^1].flow+=tmp;
if(res<=0)break;
}
return lim-res;
}
inline int Dinic()
{
int res=0,cost=0;
while(spfa())
{
int flow=dfs(S,inf);
res+=flow,cost+=dis[T]*flow;
}
return cost;
}
int main()
{
scanf("%d%d",&n,&m);
S=0,T=2*n+1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int u,v,w;scanf("%d%d%d",&u,&v,&w);
if(u>v)swap(u,v);
addflow(u,v+n,1,w);
}
for(int i=1;i<=n;i++)addflow(S,i,1,0),addflow(S,i+n,1,a[i]),addflow(i+n,T,1,0);
printf("%d
",Dinic());
return 0;
}