flood

През 2005 година в Румъния станаха големи наводнения. Стотици мостове рухнаха, стотици пътища бяха разрушени.
Министър-председателят свика съвет за извънредни ситуации, който анализира картата на страната. На картата са отбелязани
N важни района. Районите са номерирани с числата от 1 до N. Отбелязани са също, както съществуващите пътища, по които може да се минава, така и разрушените пътища, като за всеки разрушен път са известни разходите за възстановяването му.
Министър-председателят иска да се възстановят минимален брой пътища, така че  да бъдат възстановени връзките между отбелязаните
N района. Ако има повече от едно решение с минимален брой пътища, ще бъде предпочетено онова, за което общите разходи за възстановяване са най-малки.

Задача

Определете пътищата, които трябва да се възстановят, както и минималните разходи, които трябва да бъдат направени.

Вход

Входният файл  flood.in  съдържа на първия ред цяло положително число N, представляващо броя на районите.
Вторият ред на файла съдържа цяло неотрицателно число
M, представляващо броя на съществуващите пътища, по които може да се минава.
Всеки от следващите
M реда съдържа две цели положителни числа, X и Y, които са от 1 до N, разделени с интервал, означаващи, че между районите X и Y съществува път, по който може да се преминава.
Следващият ред съдържа цяло неотрицателно число
P, представляващо броя на разрушените пътища.
Всеки от следващите
P реда съдържа три цели положителни числа, разделени с интервали, X, Y и C, което означава, че възстановяването на пътя от X до Y ще струва C евро.

Изход

Изходният файл  flood.out  трябва да съдържа на първия ред цяло неотрицателно число nr, представляващо минималния брой пътища, които трябва да бъдат възстановени. На втория ред на изходния файл трябва да бъде записано цяло неотрицателно число S, представляващо сумата от разходите за възстановяване на избраните nr пътища (възможно най-малката). Всеки от следващите nr реда трябва да съдържа по три цели положителни числа, разделени с интервал,  X Y C, със смисъл, че  "пътят между X и Y с цена C ще бъде възстановен".

Ограничения

Пример

 

flood.in

flood.out

6
4
1 2
1 6
3 4
3 5
3
2 5 3
1 3 5
4 5 1

1
3
2 5 3

Ограничение за време: 0.6секунди на тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.
cerchez@gmail.com

Превод на български: Стоян Капралов