Telefono linija

Pradinių duomenų failas:

linija.in  

Rezultatų failas:

linija.out  

Laiko apribojimas:

2 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Lino telefono linijų kompanija Lintel neseniai buvo pasamdyta Teo modernizuoti telefono linijų infrastruktūrą visoje Lietuvoje, ypač mažose gyvenvietėse bei kaimuose. Teo yra numačiusi aibę centrų, kuriuos reikia sujungti telefono linijomis taip, kad kiekviena pora centrų būtų sujungta, tiesiogiai arba netiesiogiai. Lintel darbas yra nustatyti, kaip sujungti šiuos centrus, bei atlikti darbą.

Kelis mėnesius tyrę situaciją, Lintel ekspertai apskaičiavo, kuriuos centrus tarpusavyje įmanoma sujungti telefono linija, bei kiek tai kainuotų. Be to, jie nustatė, kad kai kurie centrai jau yra sujungti pakankamai moderniomis telefono linijomis – jas būtų galima panaudoti ir ateityje (tačiau Teo apie tai nebūtina žinoti, tuojau paaiškės, kodėl).

Prieš pradedant darbą, Teo patvirtins projektą ir skirs reikiamą sumą pinigų. Teo reikalauja, kad tokio jungimo schema nebūtų perteklinė: kiekvieną centrų porą jungtų ne daugiau negu viena linija (tiesioginė arba netiesioginė). Kelias dienas pasivaikščiojęs iš kampo į kampą Linas nusprendė, kad tai tikrai nebloga proga pasipelnyti! Jis įsitikinęs, kad Teo, būdami biurokratai, po projekto patvirtinimo nebesikiš į Lintel darbą, ir jiems terūpės darbo rezultatas – jungus centrų tinklas. Taigi nunešti patvirtinimui galima vienokį projektą, o realiai įgyvendinti pigesnį. Tačiau kiek daugiausiai pinigų galima šitaip uždirbti?.. Va va, pagaliau pareiname prie esmės.

Pasikasęs pakaušį Linas nusprendė, kad išspręsti šią problemą turite Jūs! Parašykite programą, kuri rastų, kiek galima pasipelnyti, įgyvendinus šią aferą.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje pateikiamas centrų, kuriuos numatyta sujungti skaičius N (1 <= N <= 1000).

Sekančioje eilutėje įrašytas skaičius M – tai porų, kurias galima jungti tarpusavyje skaičius. Toliau seka M eilučių, kuriose įrašyti sveikų skaičių trejetai a, b ir K, žymintys, kad poros (a, b) tiesioginio sujungimo kaina yra K (1 <= K <= 10000).

Sekančioje eilutėje įrašytas skaičius P. Toliau seka P centrų, kurie jau yra tiesiogiai sujungti moderniomis telefono linijomis, porų. Šios poros visuomet bus prieš tai išvardintų porų poaibis.

Rezultatai

Į pirmąją rezultatų failo eilutę turi būti įrašoma didžiausia suma, kurią gali uždirbti Lintel.

Pavyzdžiai

6
8
1 2 300
1 3 100
1 6 1000
2 4 400
3 4 500
3 5 100
4 6 100
5 6 200
1
1 6

1800