eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

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

Вважається, що в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 , якщо мережу побудувати неможливо.

Приклад

Вхідні дані #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
Вихідні дані #1
110.25 UAH
Джерело III етеп Всеукраїнської олімпіади з інформатики в Житомирській обл. 2016-2017 р