e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

КОМП’ЮТЕРНА МЕРЕЖА

КОМП’ЮТЕРНА МЕРЕЖА

В рамках підготовки до проведення другого туру обласної олімпіади з інформатики вирішили з’єднати усі комп’ютери у єдину комп’ютерну мережу. Відомо, що існують окремі з’єднання комп’ютерів, або окремі локальні мережі, які об’єднують певні комп’ютери.

Вважається, що вcі комп’ютери знаходяться в єдиній мережі, якщо існує шлях у мережі між будь-якою парою комп’ютерів.

У вхідному файлі записані вартості робіт по з’єднанню i -ого комп’ютера з j - им (числа можуть бути як цілими, так і дробовими). Також вказано, які комп’ютери вже з’єднані.

Визначте мінімальну вартість робіт, які потрібно виконати, щоб з’єднати усі комп’ютери у мережі або виведіть No, якщо цього зробити неможливо.

Вхідні дані:

У першому рядку записані числа N - кількість комп’ютерів (**_2 <= N <= 1000_**), M - кількість пар комп’ютерів, вартості з’єднання яких відомі (**_2 ≤ M ≤ N*(N-1)/2_**), K - кількість з’єднань комп’ютерів, які вже існують (**_2 ≤ K ≤ N*(N-1)/2_**).

У наступних M рядках записано по 3 числа (номери комп’ютерів, які можна з’єднати і вартість з’єднання). Далі розміщено K рядків, у яких вказано по два числа - номери комп’ютерів, які вже з’єднані.

Вихідні дані:

Вартість робіт у гривнях з точністю до копійок у форматі: _XXX.XX UAH_ (відповідь вказується без початкових нулів і обов’язково з двома знаками після крапки). Якщо відповіддю є значення 0, то потрібно вивести _0.00 UAH_ , або рядок No , якщо мережу побудувати неможливо.

Time limit 1 second
Memory limit 64 MiB
Input example #1
5 5 2
1 2 100.00
1 3 70.15
1 5 70.25
2 3 100
2 4 40
1 2
1 3
Output example #1
110.25 UAH
Source III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2016-2017 р