spfa求最小费用流
边用过之后变成反向负费用流
spfa两次后输出。
var
  bb:boolean;
  g,c:array[1..1004,0..1004] of longint;
  father,fatherc:array[1..1004] of longint;
  v:array[1..1004] of boolean;
  d,q:array[1..1004] of longint;
  cost,maxflow,n,m,i,j,k,x,y,z,head,tail,s,t,lin:longint;
procedure spfa(s:longint);
begin
  for i:=1 to n do
    d[i]:=maxlongint;
  d[s]:=0;
  head:=0;
  tail:=1;
  q[1]:=s;
  fillchar(v,sizeof(v),false);
  v[s]:=true;
  repeat
    head:=head mod 1000+1;
    k:=q[head];
    for i:=1 to g[k,0] do
        if d[g[k,i]]-c[k,i]>d[k] then
          begin
          d[g[k,i]]:=d[k]+c[k,i];
          father[g[k,i]]:=k;
	  fatherc[g[k,i]]:=i;
          if not v[g[k,i]] then
          inc(tail);
          q[tail]:=g[k,i];
          v[g[k,i]]:=true;
          end;
    v[k]:=false;
  until head=tail;
end;
begin
  readln(n,m);
  lin:=0;
  fillchar(g,sizeof(g),0);
  fillchar(c,sizeof(c),0);
  for i:=1 to m do
    begin
      readln(x,y,z);
      inc(g[x+1,0]);
      g[x+1,g[x+1,0]]:=y+1;
      c[x+1,g[x+1,0]]:=z;
      inc(g[y+1,0]);
      g[y+1,g[y+1,0]]:=x+1;
      c[y+1,g[y+1,0]]:=z;
    end;
  g[1,0]:=1;
  g[1,1]:=2;
  c[1,1]:=0;
  inc(n,2);
  inc(g[n-1,0]);
  g[n-1,g[n-1,0]]:=n;
  c[n-1,g[n-1,0]]:=0;
  s:=1;
  t:=n;
  bb:=false;
  cost:=0;
  repeat
  spfa(s);
  cost:=cost+d[t];
  x:=father[t];
  y:=t;
  repeat
    if (x<>s) and (y<>t) then
      begin

        c[x,fatherc[y]]:=maxlongint;
        for i:=1 to g[y,0] do
		  if g[y,i]=x then
		    c[y,i]:=-c[y,i];
      end
      else
       begin
         inc(lin);
         if lin=2 then
           begin
             writeln(cost);
             halt;
           end;
       end;

       y:=x;
    x:=father[x];
  until x=s;
  until bb;
end.