记录编号	138	评测结果	AAATT
题目名称	公路建设	最终得分	30
用户昵称	thegy	是否通过	未通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-04-25 22:12:14	内存使用	0.00 MiB

program road;
var
  n,m,k,i,j,ans,a,b,c,p,max,d,e:longint;
  fin,fout:text;
  flag:boolean;
  g:array[1..500,1..500]of longint;
  v:array[1..500]of boolean;
  fa:array[1..500]of longint;
procedure dfs(x:longint);
var
  i:longint;
begin
  v[x]:=true;
  for i:=1 to n do
  begin
    if not(v[i]) and (g[i,x]<>9999999) then
    begin
      fa[i]:=x;
      dfs(i);
    end;
  end;
end;

function lian(x,y:longint):boolean;
begin
  for i:=1 to n do v[i]:=false;
  dfs(x);
  if v[y] then lian:=true else lian:=false;
end;


procedure find(x,y:longint;var xx,yy:longint);
var
  i:longint;
begin
  for i:=1 to n do v[i]:=false;
  dfs(x);
  p:=y;
  max:=0;
  repeat
    if g[p,fa[p]]>max then
    begin
      max:=g[p,fa[p]];
      xx:=p;
      yy:=fa[p];
    end;
    p:=fa[p];
  until p=x;
end;

begin
  assign(fin,'road.in'); reset(fin);
  assign(fout,'road.out'); rewrite(fout);
  read(fin,n,m);
  flag:=false;
  for i:=1 to n do
  for j:=1 to n do
  begin
    g[i,j]:=9999999;
  end;
  ans:=0;
  for k:=1 to m do
  begin
    read(fin,a,b,c);

//*******************************************

    if lian(a,b) then
    begin
      find(a,b,d,e);
      if g[d,e]>c then
      begin
        ans:=ans-g[d,e]+c;
        g[d,e]:=9999999;
        g[e,d]:=9999999;
        g[a,b]:=c;
        g[b,a]:=c;
      end;
    end
    else
    begin
      g[a,b]:=c;
      g[b,a]:=c;
      inc(ans,c)
    end;

//*******************************************

    if not(flag) then
    begin
      for i:=1 to n do v[i]:=false;
      dfs(1);
      flag:=true;
      for i:=1 to n do if not(v[i]) then
      begin
        flag:=false;
        break;
      end;
      if flag then
        writeln(fout,(ans/2):0:1)
      else writeln(fout,'0');
    end
    else writeln(fout,(ans/2):0:1);

//*******************************************
  end;
  close(fout);
end.