记录编号	39093	评测结果	AWWWWWWWWT
题目名称	危险游戏	最终得分	10
用户昵称	fuhao	是否通过	未通过
代码语言	Pascal	运行时间	1.097 s
提交时间	2012-07-04 16:35:52	内存使用	6.39 MiB

const much=100000; maxn=10001; maxt=100001;
var
 tt,ans,j,i,n,t,f1,f2,kx,ky,q,x,y,z:longint;
 fa,a,b:array[0..maxn] of longint;
 f,ff:array[0..maxt,1..4] of longint;
 next,link,cost,pre:array[0..much*2] of longint;
 v:array[0..maxn] of boolean;
 found:boolean;
 procedure change(var x,y:longint);
 var t:longint;
 begin t:=x; x:=y; y:=t; end;
 procedure kp(l,r:longint);
 var i,j,mid:longint;
 begin
  i:=l; j:=r; mid:=f[(l+r) shr 1,3];
  repeat
   while f[i,3]<mid do inc(i);
   while f[j,3]>mid do dec(j);
   if i<=j then
    begin
     change(f[i,1],f[j,1]);
     change(f[i,2],f[j,2]);
     change(f[i,3],f[j,3]);
     change(f[i,4],f[j,4]);
     inc(i); dec(j);
    end;
  until i>j;
  if i<r then kp(i,r);
  if l<j then kp(l,j);
 end;
 function sf(k:longint):longint;
 begin
  if k<>fa[k] then fa[k]:=sf(fa[k]) else fa[k]:=k;
  sf:=fa[k];
 end;
 procedure insert(x,y,z,k:longint);
 var tot:longint;
 begin
  inc(tt); tot:=tt+k;
  next[tot]:=a[x]; a[x]:=tot;
  pre[tot]:=0; pre[next[tot]]:=tot; link[tot]:=y;
  cost[tot]:=z;
 end;
 procedure kruscal;
 var i,j:longint;
 begin
  j:=0;
  for i:=1 to t do
   begin
    f1:=sf(f[i,1]); f2:=sf(f[i,2]);
    if f1<>f2 then
     begin fa[f1]:=f2; ans:=ans+f[i,3]; inc(j);
           insert(f[i,1],f[i,2],f[i,3],0);
           insert(f[i,2],f[i,1],f[i,3],much);
     end;
    if j=n-1 then break;
   end;
 end;
 procedure dfs(k,aim:longint);
 var i:longint;
 begin
  v[k]:=true;
  inc(b[0]); b[b[0]]:=k;
  i:=a[k];
  while i<>0 do
   begin
    if not v[link[i]] then
     begin
      if link[i]=aim then found:=true;
      if found then
        begin
         if cost[i]>cost[kx] then kx:=i;
         exit;
        end;
      dfs(link[i],aim);
      if found then
        begin
         if cost[i]>cost[kx] then kx:=i;
         exit;
        end;
     end;
    if found then exit;
    i:=next[i];
   end;
  if found then exit;
 end;
begin
 assign(input,'tubea.in'); reset(input);
 assign(output,'tubea.out'); rewrite(output);
 readln(n,t);
 for i:=1 to t do
  begin
   readln(ff[i,1],ff[i,2],ff[i,3]);
   ff[i,4]:=i;
  end;
 f:=ff;
 kp(1,t);
 for i:=1 to n do fa[i]:=i;
 kruscal;
 writeln(ans);
 read(q);
 for i:=1 to q do
  begin
   read(kx,ky);
   x:=ff[kx,1]; y:=ff[kx,2]; z:=ky;
   for j:=1 to b[0] do v[b[j]]:=false;
   kx:=0; ky:=0; b[0]:=0; found:=false;
   dfs(x,y);
   if kx<>0 then
   begin
    if kx<=n-1 then ky:=kx+much else ky:=kx-much;
    if next[kx]<>0 then
     pre[next[kx]]:=pre[kx];
    if pre[kx]<>0 then
     next[pre[kx]]:=next[kx];
    if next[ky]<>0 then
     pre[next[ky]]:=pre[ky];
    if pre[ky]<>0 then
     next[pre[ky]]:=next[ky];
    ans:=ans-cost[kx]+z;
    insert(x,y,z,0); insert(y,x,z,much);
   end;
   writeln(ans);
  end;
 close(input); close(output);
end.