看到这道题不难想到费用流吧，但是怎么做呢？
一开始看到“每个点都恰好走一次”，我首先想到的有下界最小费用流，
然后发现这没有满足最大流的条件，然后又连边松弛掉多余的流
为了按照可行流的做法先减减去极大再加上极大，我又开了int64
最后弄啊弄，AC了倒是，但是跑出了一个很恶心的14s+，
感觉不是这样做，仔细想想，每个点都恰好走一次，并且这是一个DAG图----->最小路径覆盖！
这才正解，只不过这里是带费用的，其实也没什么
首先我们先不管瞬移模式，先按拆点
对于图上的边(i,j)，连边i--->j' 流量为1，费用为边长
然后添加超级源汇，源汇和两部分点连边
下面考虑瞬移，连边s---->i' 流量为1，费用为瞬移时间
这样就搞定了
const inf=; type node=record
flow,point,next,cost:longint;
end; var edge:array[..] of node;
d,a:array[..] of longint;
p,pre,cur:array[..] of longint;
q:array[..] of longint;
v:array[..] of boolean;
z,ans,m,x,y,i,j,n,s,t,len:longint; procedure add(x,y,f,w:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=w;
edge[len].next:=p[x];
p[x]:=len;
end; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; function spfa:boolean;
var i,f,r,x,y:longint;
begin
for i:= to t do
d[i]:=inf;
d[]:=;
fillchar(v,sizeof(v),false);
v[]:=true;
f:=;
r:=;
q[]:=;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
if d[y]>d[x]+edge[i].cost then
begin
d[y]:=d[x]+edge[i].cost;
pre[y]:=x;
cur[y]:=i;
if not v[y] then
begin
inc(r);
q[r]:=y;
v[y]:=true;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=inf then exit(false) else exit(true);
end; procedure mincost;
var i,j:longint;
begin
while spfa do
begin
i:=t;
while i<> do
begin
j:=cur[i];
dec(edge[j].flow);
inc(edge[j xor ].flow);
i:=pre[i];
end;
ans:=ans+d[t];
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
for i:= to n do
read(a[i]);
for i:= to m do
begin
readln(x,y,z);
if x>y then swap(x,y);
add(x,y+n,,z);
add(y+n,x,,-z);
end;
t:=*n+;
for i:= to n do
begin
add(,i+n,,a[i]);
add(i+n,,,-a[i]);
add(,i,,);
add(i,,,);
add(i+n,t,,);
add(t,i+n,,);
end;
mincost;
writeln(ans);
end.