Задача D. Наводнение
---
В един град има n кръстовища, някои от които са свързани с преки двупосочни улици. Между две кръстовища може да има повече от една пряка улица. През пролетта има големи наводнения заради прииждащата река и някои от улиците остават под вода. За всяка улица е известно времето, за което общинската фирма ще успее да я почисти. Необходимо е част от наводнените улиците да се изчистят от придошлата вода, за да може да се достига от всяко кръстовище до всяко друго. Задачата на общинската фирма е за минимално време на осигури възможност за достигане от всяко кръстовище до всяко друго.

Напишете програма flood, която по дадени n кръстовища и m улици, намира минималното време, за което общинската фирма ще се справи със задачата. Програмата трябва да обработва няколко тестови случаи.

Вход
---
От първия ред на стандартния вход се въвежда броят на тестовите случаи. За всеки тестов случай следват няколко реда. Първият от тях съдържа три числа 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