В Ужмісті - столиці Ужляндії, планується провести фестиваль Ужляндських виробів. Президент Ужляндії розуміє, що гості з усіх куточків Ужляндії приїдуть на цей фестиваль і хоче зробити їх подорож як можна менш витратною.
Ужляндія складається з міст. Дорожна система Ужляндії не змінювалася з давніх пір, і тому вона містить лише N-1 двонапрямлених доріг. По цих дорогах все ще можна проїхати з будь-якого міста Ужляндії в будь-яке інше (можливо, через проміжні міста). Історично, за проїзд по кожній дорозі стягується податок. Він стягується одним з міст, що з'єднуються дорогою. Кажуть, що це місто відповідальне за цю дорогу. Величина податку може бути різною для різних доріг.
Для проїзду до столиці деяким жителям Ужляндії необхідно заплатити більше, а іншим менше. Це впливає на атмосферу свята: той, кому довелося заплатити занадто багато, приїжджає без настрою. Президент хоче мінімізувати суму дорожнього податку, яку потрібно заплатити на шляху до столиці з будь-якого міста Ужляндії. Для цього він вирішив наказати усім містам скасувати податок на одній з доріг, за які вони відповідальні. Якщо місто не відповідальне за жодну дорогу, то і скасовувати податок йому не потрібно.
Допоможіть визначити, на яких дорогах потрібно скасувати податок, щоб вартість подорожі до столиці стала якомога менша. Вартість подорожі до столиці визначається як максимальне значення для всіх міст Ужляндії.
Перший рядок вхідного файлу містить ціле число (2 \leq N \leq 10^3) — кількість міст в Ужляндії. Міста пронумеровані натуральними числами від до , Ужмісто має номер . Далі йдуть N-1 рядків. Кожен з цих рядків містить три розділених одиночними пробілами цілих числа , , : між містами з номерами і є дорога, за яку відповідальне місто з номером , і за проїзд по якій стягується податок рівний (1 \leq Z \leq 10^4).
Єдиний рядок вихідного файлу має містити одне ціле число — мінімально можливе значення суми податків на шляху з міста в столицю.
Example 1
Example 2
N \leq 10 — не менше 20 балів
N \leq 20 — не менше 30 балів
N \leq 200 — не менше 50 балів
N \leq 2000 — не менше 70 балів