Tasks:
 
Task DescriptionDiscussion (0)
Task :: 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.

Ulaz:

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.

Izlaz:

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

Primer:

Ulaz:
7 8 3
1 2 5
1 4 8
3 2 3
4 3 2
4 5 3
5 6 6
5 7 3
6 7 9
2 5
1 3
5 7

Izlaz:
6

Objašnjenje:



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
Submit Solution
:
:
Available Languages
Task info
Name:struja
Time:1 sec.
Memory:16 MB
#Tests:10
Author:Igor Kabiljo
AddedBy: admin
Task Ratings
Difficulty:

4.5 (12 votes)
Quality:

4.3 (13 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
davidmilicevic97 0.161 s.
gvolarevic 0.211 s.
mkostelac 0.227 s.
njagar 0.23 s.
The_Philosopher 0.235 s.
zvoc2510 0.241 s.
zvoc333 0.244 s.
nikola_12345 0.25 s.
Delta3 0.265 s.
johndoe 0.266 s.
Solved By