E2 - Internetový terorizmus ☠

Jano sa dal na dráhu interornetizmu. Ako vstupný test do organizácie zastrešujúcej dané odvetvie dostal za úlohu narušiť celistvosť siete prerušením niektorých vedení (teda zamedziť niekomu prístup k lokalite, ku ktorej prístup normálne má). No v momente, ked preruší prvé, vyhlásia v internetovej polícii (interpol) poplach a pri pokuse o sabotáž ďalšieho by ho už chytili (čo je aj dôvod prečo interornetisti sa organizujú - presne časovaný distribuovaný útok). Problém ale je, že mnoho vedení má zálohu (je viacnásobná alebo sa dá nahradiť obkľukou) a tak keď preruší spoj Malajzia - Taiwan, Malajzijčania majú stále možnosť pripojiť sa kamkoľvek cez Austráliu a v konečnom dôsledku by Jano nikoho neinterornetizoval.
Jano si zostavil mapu celosvetovej konektivity, aj so zaznačením stupňa ochrany a prístupnosti jednotlivých spojov. Stupeň 0 majú spoje ku ktorým sa takmer nemá šancu dostať, s narastajúcim číslom klesá úroveň ich ochrany.
Teraz potrebuje zistiť, aký stupeň ochrany má najslabšie zabezpečený kritický spoj (taký, ktorý by mu zaručil členstvo).

Úloha

Máme daný zoznam N spojov aj so stupňom ochrany. Vašou úlohou je zistiť stupeň ochrany najmenej zabezpečeného kritického spojenia.

Vstup

V prvom riadku súboru sa nachádza prirodzené číslo N ktoré udáva počet spojov.

Nasleduje N riadkov udávajúcich spojenia, pričom v každom sa nachádzajú identifikátory koncových uzlov Z, K a 9(celočíselný) stupeň ochrany S

E1

1 ≤ N ≤ 1000

E2

1 ≤ N ≤ 10⁶

Výstup

Výstupom programu je stupeň ochrany najmenej zabezpečeného kritického spojenia, alebo -1, ak neexistuje žiaden kritický spoj.

Príklady

Vstup:

5
1 2 1
2 3 15
2 4 0
3 4 10
3 4 888

Výstup:

1

Vstup:

2
1 2 10
3 4 11

Výstup:

11