type alice=record

x,y,f,c,next,op:longint;

end;

var tot,n,a,b,c,d,cost,x,i,k,del,now,head,tail,s,t:longint;

bian:array[-10..10000]of alice;

first,q,w,pre:array[-10..10000]of longint;

v:array[-10..10000]of boolean;

procedure connect(a,b,c,d:longint);

begin

inc(tot);

bian[tot].x:=a;

bian[tot].y:=b;

bian[tot].f:=c;

bian[tot].c:=d;

bian[tot].op:=tot+1;

bian[tot].next:=first[a];

first[a]:=tot;

inc(tot);

bian[tot].x:=b;

bian[tot].y:=a;

bian[tot].f:=0;

bian[tot].c:=-d;

bian[tot].op:=tot-1;

bian[tot].next:=first[b];

first[b]:=tot;

end;

procedure main;

begin

while 1=1 do

begin

for i:=1 to n do w[i]:=maxlongint;

head:=0; tail:=1;

q[1]:=s; v[s]:=true; w[s]:=0;

repeat

inc(head);

x:=q[head];

k:=first[x];

while k<>0 do with bian[k] do

begin

if f>0 then

if w[y]>w[x]+c then

begin

w[y]:=w[x]+c;

pre[y]:=k;

if not v[y] then

begin

inc(tail);

q[tail]:=y;

v[y]:=true;

end;

end;

k:=next;

end;

v[x]:=false;

until head=tail;

if w[t]=maxlongint then break;

now:=t; del:=maxlongint;

while now<>s do with bian[pre[now]] do

begin

if f<del then del:=f;

now:=x;

end;

now:=t;

while now<>s do with bian[pre[now]] do

begin

dec(f);

inc(bian[op].f);

now:=x;

end;

inc(cost,del*w[t]);

end;

writeln(cost);

end;

begin

assign(input,'ex.in');

assign(output,'ex.out');

reset(input);

rewrite(output);

fillchar(v,sizeof(false),false);

cost:=0;

readln(n);

s:=1;t:=n;

readln(a,b,c,d);

while (a<>0)and(b<>0) do

begin

connect(a,b,c,d);

readln(a,b,c,d);

end;

main;

close(input);

close(output);

end.

用spfa求最小费用最大流，不过？