There are several test cases.
Each test case will starts with three numbers n , m, and p in one line, n stands for the number of monks and m stands for the number of places that can been used, p stands for the number of roads between these places. The places the monks stay is signed from 1 to n then the other m places are signed as n + 1 to n + m. (1 <= n <= 5, 0 <= m <= 1000, 0 <=p <= 5000)
Then n + m numbers followed which stands for the value of digging a well in the ith place.
Then p lines followed. Each line will contains three numbers a, b, and c. means build a road between a and b will cost c.