类似于最短路的网络流，而且还要保证每个点经过一次，拆点就比较方便了。
连边怎么连？要保证最大流是n（每个点经过一次）还要能从直接跳转
将每个点拆点。
源点向每个点的入点连一条容量为1费用为0的边。
源点向每个点的出点连一条容量为1费用为瞬移到该点所需时间的边。
每个点的出点向汇点连一条容量为1费用为0的边。
对于每条边(i,j)，从i点入点向j点出点连一条容量为1费用为航路所需时间的边。
就是，到了每个点，出点会标记到了这个点（连向T一条边的流量会流过去）
走从S到一个点x的入点边，相当于选择从这个点x走要一条边到达另一个点
走。。。。。。。出点边，相当于直接瞬移。
费用都是正的，所以每个点一定被经过恰好一次。
把这些流按一定顺序排序，走出来的一定就是一个合法的路径。
流到该点出点的某入点对应的星球，在之前的某一时刻一定由某种合法方式达到过，追溯到头一定是某个瞬移到的点（因为图中没有环），“追溯”的过程就是这一条路径。
#include<bits/stdc++.h>
#define il inline
#define reg register int
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=;
const int M=+;
const int inf=0x3f3f3f3f;
int n,m,s,t;
struct node{
int nxt,to;
int w,v;
}e[*(N+M+N)];
int hd[N],cnt=;
void add(int x,int y,int w,int v){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
e[cnt].w=w;
e[cnt].v=v;
hd[x]=cnt; e[++cnt].nxt=hd[y];
e[cnt].to=x;
e[cnt].w=;
e[cnt].v=-v;
hd[y]=cnt;
}
int incf[N],dis[N];
int pre[N];
bool vis[N];
queue<int>q;
bool spfa(){
while(!q.empty()) q.pop();
memset(vis,,sizeof vis);
memset(dis,inf,sizeof dis);
dis[s]=;
incf[s]=inf;
pre[s]=;
q.push(s);
while(!q.empty()){
int x=q.front();q.pop();
vis[x]=;
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(e[i].w&&dis[y]>dis[x]+e[i].v){
dis[y]=dis[x]+e[i].v;
pre[y]=i;
incf[y]=min(e[i].w,incf[x]);
if(!vis[y]){
vis[y]=;
q.push(y);
}
}
}
}
if(dis[t]==inf) return false;
return true;
}
int ans,maxflow;
void upda(){
int x=t;
while(pre[x]){
e[pre[x]].w-=incf[t];
e[pre[x]^].w+=incf[t];
x=e[pre[x]^].to;
}
ans+=incf[t]*dis[t];
maxflow+=incf[t];
//cout<<" ans "<<ans<<" "<<maxflow<<endl;
}
int main(){
rd(n);rd(m);
s=,t=*n+;
int x;
for(reg i=;i<=n;++i){
rd(x);
add(s,i+n,,x);
add(i+n,t,,);
add(s,i,,);
}
int y,z;
for(reg i=;i<=m;++i){
rd(x);rd(y);rd(z);
if(x>y) swap(x,y);
add(x,y+n,,z);
}
while(spfa()) upda();
//cout<<" liu "<<maxflow<<endl;
cout<<ans;
return ;
}}
signed main(){
Miracle::main();
return ;
}/*
Author: *Miracle*
Date: 2018/12/14 11:29:33
*/
