记录编号	41106	评测结果	AAAAAAATTT
题目名称	[河南省队2012] 长途奔袭	最终得分	70
用户昵称	wo shi 刘畅	是否通过	未通过
代码语言	Pascal	运行时间	3.523 s
提交时间	2012-07-20 16:16:25	内存使用	19.35 MiB

var
  n,m,i,s,t,r,ans,x,y,z:longint;
  c,w:Array[0..1000,0..1000]of longint;
  q,last,d:Array[0..1000000]of longint;
  v:Array[0..100000]of boolean;
 
procedure addpage(x,y,cc,ww:longint);
begin
  c[x,y]:=cc;
  w[x,y]:=ww;
  w[y,x]:=-ww;
end;
 
function spfa:boolean;
var
  i,head,tail,x:longint;
begin
  for i:=s to t do
  begin
    d[i]:=maxlongint div 2;
    last[i]:=-1;
    v[i]:=false;
  end;
  head:=1;
  tail:=1;
  q[1]:=s;
  d[s]:=0;
  v[s]:=true;
  repeat
    x:=q[head];
    for i:=s to t do
    if (c[x,i]>0)and(d[x]+w[x,i]<d[i]) then
    begin
      d[i]:=d[x]+w[x,i];
      last[i]:=x;
      if not v[i] then
      begin
        v[i]:=true;
        inc(tail);
        q[tail]:=i;
      end;
    end;
    inc(head);
    v[x]:=false;
  until head>tail;
  if d[t]=maxlongint div 2 then exit(false);
  exit(true);
end;
 
procedure goformin;
var
  i:longint;
begin
  r:=maxlongint;
  i:=t;
  repeat
    if c[last[i],i]<r then r:=c[last[i],i];
    i:=last[i];
  until last[i]=-1;
end;
 
procedure change;
var
  i:longint;
begin
  i:=t;
  repeat
    dec(c[last[i],i],r);
    inc(c[i,last[i]],r);
    i:=last[i];
  until last[i]=-1;
  inc(ans,r*d[t]);
end;
 
begin
  assign(input,'YZ.in'); reset(input);
  assign(output,'YZ.out'); rewrite(output);
  readln(n,m);
  s:=0;
  t:=n+n+1;
  for i:=1 to n do
  begin
    read(x);
    addpage(s,n+i,1,x);
    addpage(s,i,1,0);
    addpage(n+i,t,1,0);
  end;
  for i:=1 to m do
  begin
    readln(x,y,z);
    if y<x then addpage(y,n+x,1,z)
    else addpage(x,n+y,1,z);
  end;
  while spfa do
  begin
    goformin;
    change;
  end;
  writeln(ans);
  close(input);
  close(output);
end.