var
  t,n,m,ans,j,time,x,y,i:longint;
  last,q,d,f,a:array[0..100000]of longint;
  c:array[0..100,0..100]of longint;


procedure bfs;
var
  h,t,x,i:longint;
begin
  h:=1;
  t:=1;
  for i:=0 to n do d[i]:=-1;
  for i:=0 to n do f[i]:=0;
  q[1]:=0;
  d[0]:=0;
  repeat
    x:=q[h];
    for i:=0 to n do
    if (c[x,i]>0)and((d[i]=d[x]+1)or(d[i]=-1)) then
    begin
      if d[i]=-1 then
      begin
        inc(t);
        q[t]:=i;
      end;
      d[i]:=d[x]+1;
      inc(f[x]);
    end;
    inc(h);
  until h>t;
end;

procedure dfs;
var
  top,i,x,min:longint;
begin
  top:=1; q[top]:=0;
  for i:=0 to n do last[i]:=0;
  while top>0 do
  begin
    x:=q[top];
    if x<>n then
    begin
      if f[x]>0 then
      begin
        for i:=last[x]+1 to n do
        if (c[x,i]>0)and(d[i]=d[x]+1) then
        begin
          inc(top);
          q[top]:=i;
          last[x]:=i;
          dec(f[x]);
          break;
        end;
      end
      else begin
        q[top]:=0;
        dec(top);
      end;
    end
    else begin
      min:=maxlongint;
      for i:=1 to top-1 do
      if c[q[i],q[i+1]]<min then min:=c[q[i],q[i+1]];
      inc(ans,min);
      for i:=1 to top-1 do
      begin
        dec(c[q[i],q[i+1]],min);
        inc(c[q[i+1],q[i]],min);
      end;
      i:=1;
      while c[q[i],q[i+1]]>0 do inc(i);
      top:=i;
    end;
  end;
end;

begin
  assign(input,'snipers.in'); reset(input);
  assign(output,'snipers.out'); rewrite(output);
  readln(t);
  for time:=1 to t do
  begin
    readln(n,m);
    for i:=1 to n-1 do read(a[i]);
    a[n]:=maxlongint;
    for i:=0 to n do
     for j:=0 to n do
     c[i,j]:=-1;
    for i:=1 to m do
    begin
      readln(x,y);
      c[x,y]:=a[y];
    end;
    ans:=0;
    repeat
      bfs;
      if d[n]=-1 then break;
      dfs;
    until false;
    writeln(ans);
  end;
  close(input);
  close(output);
end.