struja

U Bajtoviji Ðurica je odlucio da uvede struju. Spojio je n kuca pomocu m dalekovoda razlicitog kvaliteta. Za svaki dalekovod se zna posle koliko sati neodržavanja zarda i prestaje da provodi struju. Ispostavilo se da bi, kad bi pustio mrežu u rad, došlo do kratkog spoja i velike katastrofe. Zato je Ðurica uposlio Draganceta da ispita mrežu. Dragance je ispostavio Ðurici izveštaj, u kome se nalazi spisak k parova kuca koje ne smeju medusobno da budu spojene (ni direktno dalekovodom, ni preko drugih kuca) da bi mreža smela da se pusti u rad. Ðurica može da bira koje dalekovode ce da nastavi da održava, a koje ne. Ðurica vas je uposlio da odredite koliko najmanje sati mora da prode da bi mogao da pusti mrežu u rad, a Draganceta za teži deo posla, da ispita koje dalekovode da održava, a koje ne, na osnovu vašeg izveštaja.<br><br>

Ulaz:<br><br>

Sa prvog reda standardnog ulaza ucitava se prirodni brojevi n, m i k (1 <= n, k <= 10000, 1 <= m <= 100 000). U sledecih m redova nalaze se po tri broja i, j, kv koja oznacavaju da su kuce i i j spojene dalekovodom kvaliteta kv (1 <= kv <= 1 000 000 000, posle kv sati prestaje da propušta struju ako se ne održava). Zatim se u preostalih k redova nalazi po dva broja i i j, koja oznacavaju da kuce i i j ne smeju biti spojene, da bi mreža smela da se pusti u rad. Nijedan par gradova nije spojen direktno više od jednim dalekovodom, ni 2 puta naveden na Dragancetovom spisku.<br><br>

Izlaz:<br><br>

Na standardni izlaz ispisati minimalan broj sati s koji mora da prode da bi mreža smela da se pusti u rad.<br><br>

Primer:<br><br>
Ulaz:<br>
7 8 3<br>
1 2 5<br>
1 4 8<br>
3 2 3<br>
4 3 2<br>
4 5 3<br>
5 6 6<br>
5 7 3<br>
6 7 9<br>
2 5<br>
1 3<br>
5 7<br>
<br>
Izlaz:<br>
6<br><br>

Objašnjenje:<br><br>

<img src="./tasks/struja/struja1.png"><br><br>

Opis dalekovoda iz ulaza odgovara dalekovodu prikazanom na slici iznad. Moguce je osposobiti mrežu za 6 sati, ako prestanu da se održavaju dalekovodi 1-2, 3-4, 5-6, 5-7