program Jezirka;

const
  MaxJezer = 1000;                                          {Víc jich v lese nebude ;-)}

type
  PSoused = ^TSoused;
  TSoused = record
    Konec, Zacatek: integer;
    Delka: integer;
    Dalsi: PSoused;
  end;

  TJezirko = PSoused;                                       {Jezírko má jen sousedy}
  TJezirka = array[1..MaxJezer] of TJezirko;

var
  Jezirka: TJezirka;
  Hran, Delka: integer;
  Jezirek: integer;
  I: integer;
  J, K, D: integer;                                         {Nová cesta}
  Max: PSoused;
  Zarad: boolean;

procedure Vloz(J, K, D: integer);                           {Vlož jeden směr cesty}
var
  Tmp: PSoused;
begin
  new(Tmp);
  with Tmp^ do begin
    Konec := K;
    Zacatek := J;
    Delka := D;
    Dalsi := Jezirka[J];
  end;
  Jezirka[J] := Tmp;
end;

procedure Odeber(J, K: integer);                            {Odebere cestu z J do K}
var
  Tmp, Posledni: PSoused;
begin
  Tmp := Jezirka[J];
  Posledni := nil;
  while Tmp <> nil do begin
    if (Tmp^).Konec = K then begin
      if Posledni <> nil then
        (Posledni^).Dalsi := (Tmp^).Dalsi
      else
        Jezirka[J] := (Tmp^).Dalsi;
      dispose(Tmp);
      break;
    end else
      Tmp := (Tmp^).Dalsi;
  end;
end;

{Pokusí se najít cestu a vrací nejdelší její úsek. Nevrací se zpět do Zpet}
function Cesta(Start, Cil, Zpet: integer): PSoused;
var
  Aktual, Vysledek: PSoused;
begin
  Aktual := Jezirka[Start];
  while Aktual <> nil do begin                              {Kouknout do všech}
    if (Aktual^).Konec = Cil then begin                     {Jsem tam}
      Cesta := Aktual;
      exit;
    end;
    if (Aktual^).Konec <> Zpet then begin
      Vysledek := Cesta((Aktual^).Konec, Cil, Start);
      if Vysledek <> nil then begin                         {Tudy to vede}
        {Která je delší?}
        if (Vysledek^).Delka > (Aktual^).Delka then Cesta := Vysledek
        else Cesta := Aktual;
        exit;
      end;
    end;
    Aktual := (Aktual^).Dalsi;                              {Tady to nevyšlo, co jinudy?}
  end;
  Cesta := nil;                                             {Nic nevede :-(}
end;

begin
  WriteLn('Kolik jezírek?');
  ReadLn(Jezirek);
  for I := 1 to Jezirek do
    Jezirka[I] := nil;                                      {Ještě nic nevede}
  Hran := 0;
  Delka := 0;
  while(true) do begin                                      {Nechť orají navěky}
    WriteLn('Další cesta:');
    ReadLn(J, K, D);
    Max := Cesta(J, K, 0);                                  {Je nějaká cesta?}
    if Max <> nil then begin
      if (Max^).Delka > D then begin                        {Tak, vyměnit}
        Zarad := true;
        Dec(Delka, (Max^).Delka - D);
        Odeber((Max^).Konec, (Max^).Zacatek);
        Odeber((Max^).Zacatek, (Max^).Konec);
      end else Zarad := false;                              {Ta nová se nevyplatí}
    end else begin                                          {Tudy to nejde, tu berem}
      Zarad := true;
      Inc(Hran);
      Inc(Delka, D);
    end;
    if Zarad then begin
      Vloz(J, K, D);
      Vloz(K, J, D);
    end;
    if Hran = Jezirek - 1 then Write('Jsou spojená')
    else Write('Nejsou spojená');
    WriteLn(', délka je ', Delka);
  end;
end.