题目描述
10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座α星的悠悠也是其中之一。
赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发，访问这N颗行星每颗恰好一次，首先完成这一目标的人获得胜利。
由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。
天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。
尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。
输入格式
输入文件starrace.in的第一行是两个正整数N, M。
第二行N个数A1~AN，其中Ai表示使用能力爆发模式到达行星i所需的定位时间。
接下来M行，每行3个正整数 (ui, vi, wi)，表示在编号为ui和vi的行星之间存在一条需要航行wi时间的星际航路。
输入数据已经按引力值排序，也就是编号小的行星引力值一定小，且不会有两颗行星引力值相同。
输出格式
输出文件starrace.out仅包含一个正整数，表示完成比赛所需的最少时间。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+5,M=2e5+5,inf=0x3f3f3f3f;
inline int read(){
int x=0; char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=getchar(); }
return x;
}
int nxt[M],head[N],go[M],edge[M],cost[M],tot=1;
inline void add(int u,int v,int w1,int w2){
nxt[++tot]=head[u],head[u]=tot,go[tot]=v,edge[tot]=w1,cost[tot]=w2;
nxt[++tot]=head[v],head[v]=tot,go[tot]=u,edge[tot]=0,cost[tot]=-w2;
}
int dis[N],s,t,ret;
bool vis[N];
inline bool spfa(){
memset(dis,0x3f,sizeof(dis));
queue<int>q; q.push(s),dis[s]=0,vis[s]=1;
while(q.size()){
int u=q.front(); q.pop(); vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=go[i];
if(edge[i]&&dis[v]>dis[u]+cost[i]){
dis[v]=dis[u]+cost[i];
if(!vis[v])q.push(v),vis[v]=1;
}
}
}
return dis[t]!=inf;
}
int dinic(int u,int flow){
if(u==t)return flow;
vis[u]=1;
int rest=flow,k;
for(int i=head[u];i&&rest;i=nxt[i]){
int v=go[i];
if(!vis[v]&&edge[i]&&dis[v]==dis[u]+cost[i]){
k=dinic(v,min(edge[i],rest));
if(k)ret+=k*cost[i],edge[i]-=k,edge[i^1]+=k,rest-=k;
else dis[v]=-inf;
}
}
vis[u]=0;
return flow-rest;
}
int n,m,a[N];
signed main(){
n=read(),m=read();
s=0,t=n*2+2;
int ans=0;
for(int i=1;i<=n;i++){
int x=read(); ans+=x;
add(s,i,1,0);
add(n+i,t,1,0);
add(s,i+n,1,x);
}
for(int i=1,u,v,w;i<=m;i++){
u=read(),v=read(),w=read();
ans+=w;
if(u<v)add(u,v+n,1,w);
else add(v,u+n,1,w);
}
while(spfa())while(dinic(s,inf));
cout<<ret<<endl;
}