Ергежейлілер жаңа жерасты ауылын жаңа ғана салып бітірді. Енді оның ішінде жұмыс істейтін теміржол желісін жоспарлау уақыты келді.
Ауыл $N$ қиылыстан және оларды байланыстыратын $N - 1$ туннельден тұрады. Туннельдер кез келген қиылыстан кез келген басқа қиылысқа жетуге болатындай етіп салынған. Тұйық болып табылатын әрбір қиылыста (яғни, тек бір ғана туннельмен байланысқан қиылыста) теміржол станциясы бар.
Сіздің міндетіңіз — ауылдағы пойыздардың маршруттарын анықтау. Ергежейлілердің талаптарын орындау үшін барлық станциялар жұптастырылуы керек (бақытымызға орай, олардың саны жұп), және әр жұптың арасында мүмкін болатын ең қысқа жолды пайдаланып бір пойыз қатынайтын болады. Алайда туннельдердің өз шектеулері бар. Әр туннельдің ұзындығы бірдей ($1$-ге тең) болғанымен, олардың ені арқылы тек шектеулі маршруттар саны ғана өте алады.
Ергежейлілер пойыз маршруттарының жалпы ұзындығы мүмкіндігінше ұзын болғанын қалайды. Максималды ұзындық қандай болуы мүмкін екенін есептей аласыз ба?
Кіріс деректері
Кіріс деректерінің бірінші жолында ауылдағы қиылыстар санын білдіретін бір бүтін сан $N$ берілген.
Келесі $N - 1$ жолдың әрқайсысында $a_i$ және $b_i$ қиылыстары арасындағы туннельді білдіретін үш бүтін сан $a_i$, $b_i$, $c_i$ берілген. $c_i$ мәні — осы туннель арқылы өте алатын маршруттар санының жоғарғы шегі.
Шығыс деректері
Бірінші және жалғыз жолда таңдалған станциялар жұптары арасындағы жолдардың максималды жалпы ұзындығын білдіретін бір бүтін санды шығарыңыз.
Егер шектеулерді қанағаттандыра отырып станцияларды жұптастыру мүмкін болмаса, $-1$ шығарыңыз.
Шектеулер
$2 \le N \le 200\,000$, $1 \le a_i, b_i \le N$, $0 \le c_i \le N$, барлық қиылыстар байланысқан, ал станциялардың (яғни тұйықтардың) саны жұп.
Мысалдар
Кіріс 1
10 1 2 2 2 3 1 3 4 3 5 1 1 6 1 2 7 2 3 8 3 2 9 3 1 10 4 7
Шығыс 1
10
Ескертпе
Бірінші мысалда $5\text{--}9$, $6\text{--}7$ және $8\text{--}10$ қиылыстарындағы станцияларды қосу пойыз маршруттарының $4 + 3 + 3 = 10$ болатын жалпы ұзындығын береді.
Кіріс 2
5 1 2 3 1 3 1 1 4 0 1 5 2
Шығыс 2
-1