记录编号	39326	评测结果	AAAAAAAAAA
题目名称	最小最大生成树	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.728 s
提交时间	2012-07-09 11:49:12	内存使用	21.83 MiB

program mstn;
const maxn=20001; maxm=800001;
var
 c,next,link,un:array[0..maxm] of longint;
 a,p,h,hnum:array[0..maxn] of longint;
 f:array[0..maxm,1..3] of longint;
 x,y,z,l,s,t,ans,max,n,tot,m,i:longint;
 found:boolean;
 procedure sap(k:longint);
 var i,hmin,temp:longint;
 begin
  if k=t then
   begin
    found:=true;
    ans:=ans+max;
    exit;
   end;
  hmin:=n-1; temp:=max; i:=a[k];
  while i<>0 do
   begin
    if c[i]>0 then
     begin
      if h[link[i]]+1=h[k] then
       begin
        if c[i]<max then max:=c[i];
        sap(link[i]);
        if h[s]>=n then exit;
        if found then break;
        max:=temp;
       end;
      if hmin>h[link[i]] then hmin:=h[link[i]];
     end;
    i:=next[i];
   end;
  if found then
   begin
    dec(c[i],max);
    inc(c[un[i]],max);
   end else
   begin
     dec(hnum[h[k]]);
     if hnum[h[k]]=0 then h[s]:=n;
     h[k]:=hmin+1;
     inc(hnum[h[k]]);
   end;
 end;
 procedure sapp(s:longint);
 begin
  fillchar(h,sizeof(h),0);
  fillchar(hnum,sizeof(hnum),0);
  hnum[0]:=n; h[s]:=0;
  while h[s]<=n-1 do
   begin
    found:=false;
    max:=maxlongint;
    sap(s);
   end;
 end;
 procedure insert(x,y,z:longint);
 begin
  inc(tot); next[tot]:=a[x]; a[x]:=tot;
  link[tot]:=y; c[tot]:=z; un[tot]:=tot+1;
  inc(tot); next[tot]:=a[y]; a[y]:=tot;
  link[tot]:=x; c[tot]:=0; un[tot]:=tot-1;
 end;
 procedure make_min;
 var i,j:longint;
 begin
  tot:=0;
  fillchar(a,sizeof(a),0);
  fillchar(next,sizeof(next),0);
  c:=next; un:=next; link:=c;
  for i:=1 to m do
   if f[i,3]<l then
    begin
     insert(f[i,1],f[i,2],1);
     insert(f[i,2],f[i,1],1);
    end;
  sapp(s);
 end;
 procedure make_max;
 var i,j:longint;
 begin
  tot:=0;
  fillchar(a,sizeof(a),0);
  fillchar(next,sizeof(next),0);
  c:=next; un:=next; link:=c;
  for i:=1 to m do
   if f[i,3]>l then
    begin
     insert(f[i,1],f[i,2],1);
     insert(f[i,2],f[i,1],1);
    end;
  sapp(s);
 end;
begin
 assign(input,'mstmn.in'); reset(input);
 assign(output,'mstmn.out'); rewrite(output);
 readln(n,m);
 for i:=1 to m do readln(f[i,1],f[i,2],f[i,3]);
 readln(s,t,l);
 make_min;
 make_max;
 writeln(ans);
 close(input); close(output);
end.