시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 3 3 100.000%

문제

Nekadašnji najbolji prijatelj gospodina Malnara, Aron, napustio je domovinu te je bolju budućnost potražio na jedom pustom, dalekom otoku. Zasigurno se pitate zašto je odabrao baš takvu lokaciju, a ne neki velegrad gdje će, pod okriljem neke glomazne korporacije, ostvariti veliku karijeru. Naime, bolju budućnost traži tamo gdje nema malenih paradajzića (tzv. cherry rajčica) niti ambrozije na koju je izuzetno alergičan. Kako bi mu napakostio, gospodin Malnar u svom je uredu uzgojio biljku ambrozije.

Iako ambrozija nije stablo, zanimljivo je da se biljka gospodina Malnara može prikazati kao stablo s n čvorova koji su povezani pomoću (n − 1) grana. Prisjetimo se, stablo je neusmjereni, povezani graf u kojem između svaka dva čvora postoji jedinstven put. Poznato je da su alergeni koncentrirani upravo na granama, ali nisu sve grane jednako potentne. Gospodin Malnar zna da grana koja povezuje čvorove ui i vi ima alergičnost wi . Shodno tome, iz biljke će izrezati povezani podskup grana najveće alergičnosti. Alergičnost podskupa definira se kao umnožak broja grana unutar njega sa alergičnošću najnealergičnije grane unutar tog podskupa, tj. grane s minimalnom vrijednosti wi . Gospodin Malnar je nepogrešiv i odmah je pronašao podskup s najvećom alergičnosti.

Možete li i vi odrediti alergičnost tog podskupa?

입력

U prvom je retku prirodni broj n (2 ≤ n ≤ 105).

U sljedećih se n − 1 redaka nalaze brojevi ui, vi i wi (1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 109) koji predstavljaju grane stabla kako je opisano u tekstu zadatka.

출력

U jedini redak ispišite alergičnost najalergičnijeg povezanog podskupa grana ambrozije.

예제 입력 1

10
2 4 8
5 2 7
6 3 5
3 1 1
6 7 2
9 7 3
8 6 6
8 10 7
2 6 3

예제 출력 1

18

예제 입력 2

6
3 1 11
3 5 3
4 3 2
4 2 5
2 6 7

예제 출력 2

11