Laiko ribojimas: 2s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Telefono linija

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ą.

pic

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\\leN\\le1000).

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\\leK\\le10000). Telefonų linijų planai yra kiek keisti, nes, anot jų, gali būti atvejų, kuomet tam tikrą centrą galima jungti su savimi pačiu (t.y. a=b).

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

Pradiniai duomenys Rezultatai Paaiškinimas 
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
 Oficiali jungimo schema gali kainuoti 2400 (1-2, 1-6, 2-4, 3-4, 5-6) ir neužkliūtų Teo, kadangi kiekvieną centrų porą jungtų lygiai viena linija. Tačiau realiai galima pasinaudoti jau esančia linija (1, 6) ir likusį tinklą sujungti kur kas pigiau, už 600 (1-2, 1-3, 3-5, 4-6). Gaunamas 2400 - 600 = 1800 pelnas. Tai didžiausias pelnas, kokį galima gauti šiuo atveju.