Условие

Състезание

RSOP_XXIX

Буква

D

Инфо

Flood

От първия ред на стандартния вход се въвежда броят на тестовите случаи. За всеки тестов случай следват няколко реда. Първият от тях съдържа три числа n, m и k, съответно броя на кръстовищата, общия брой на улиците и броя на улиците, които са наводнени. Всеки от следващите m реда съдържа три числа (xi, yi, ti) – номерата на кръстовищата, между които има улица и времето, за което фирмата ще почисти улицата, ако е наводнена. От следващия ред се въвеждат номерата на улиците, които са наводнени. Улиците са номерирани от 1 до m в реда, по който се въвеждат.

Изход:
За всеки тестов случай на един ред на стандартния изход програмата трябва да изведе минималното време, за което фирмата ще се справи със задачата. 

Ограничения:
1 ≤ n ≤ 1000
1 ≤ m ≤ 10000
1 ≤ k ≤ m
1 ≤ ti ≤ 30000

Примерен вход:
1
7 8 4
0 2 5
2 1 2
1 3 8
3 4 12
6 4 1
5 4 10
6 5 4
2 3 6
1 4 6 7

Примерен изход:
21

Задачи Решение Въпрос


Dimitar Minchev © 2017