Egy vállalatnál az informatikai infrastruktúra modernizálásának jegyében ún. ultravékony kliensek bevezetését tervezik: az asztali számítógépeket egy-egy végtelenül egyszerű berendezéssel helyettesítik, melyek feladata mindössze annyi, hogy a billentyűzetről és az egérről érkező bemenetet egy központi szerverre továbbítsák, majd az onnan érkező kimenetet megjelenítsék a képernyőn. A programok futtatását, illetve minden ezzel kapcsolatos számítást valójában a központi szerver végez.
A rendszernek, számos előnye mellett, hátránya, hogy érzékeny a hálózati késleltetésre. Ezért a szervert optimálisan úgy kell elhelyezni, hogy a kliensek szervertől vett késleltetéseinek maximuma minimális legyen.
Írjunk programot, mely meghatározza, hogy a szerver optimális elhelyezése esetén mekkora lesz a hálózati késleltetés a szerver és a tőle legtávolabb eső kliens között. A hálózat fatopológiájú, tehát bármely két csúcs között pontosan egy út vezet. A kliensek a hálózat végpontjaiban (a fa leveleiben) helyezkednek el, a szervert pedig valamely belső csomópontba kell telepíteni.
A program a hálózat leírását a standard bemenetről olvassa. A bemenet első sora egyetlen egész számot, a csúcsok $1\le N\le 10000$ számát tartalmazza. Az ezt követő $N-1$ sor mindegyike három, szóközzel elválasztott egész számot tartalmaz, egy-egy hálózati összekötés végpontjainak $X_i$ és $Y_i$ sorszámát ($1\le X_i\mathrm{,}{Y}_i\le N$), illetve az összekötés $0\le D_i\le 1000$ késleltetését (a két végpontbeli feldolgozáshoz szükséges idő elhanyagolható).
A program a megoldást a standard kimenetre írja, melynek egyetlen sora egyetlen $M$ egész számot tartalmazzon: az optimális szerverelhelyezés esetén a késleltetések maximumát.