8754번 - Kupiec 다국어

W Bajtlandii sieć dróg między miastami jest taka, że między dwoma dowolnymi miastami istnieje dokładnie jedna droga (bezpośrednia lub pośrednia). Pewien kupiec przyjechał do Bajtlandii w celach zarobokowych. Pierwszego dnia chciałby zamieszkać w dowolnym mieście (miasto początkowe), a następnie udać się do wybranego miasta (miasto końcowe). Kupiec na drodze z jednego miasta do drugiego nie może dwa razy odwiedzić tego samego miasta, ze względu na przepisy prawne Bajtalndii. Chciałby jednak wybrać miasto początkowe i końcowe w taki sposób, aby jego zarobek był jak największy.

Kupiec zarabia poruszając się pomiędzy miastami. Dla każdego bezpośredniego połączenia wiemy, ile bajtalarów kupiec zarobi lub straci. Pomóż wybrać kupcowi dwa miasta tak, aby jego zarobek był jak największy (w szczególności miasto początkowe i końcowe może być tym samym miastem).

W pierwszej linii wejścia znajduje się jedna liczba całkowita n (2 ≤ n ≤ 10⁶). W następnych n - 1 wierszach po trzy liczby całkowite a, b, x (-10⁹ ≤ x ≤ 10⁹), oznaczające, że istnieje bezpośrednie połączenie między miastami a i b, w którym kupiec zarobi x bajtalarów (ujemne x oznacza stratę kupca).

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba cakłkowita oznaczająca maksymalny zarobek kupca.