A rich company wants to send k kinds of jewels from their factories to destinations. Different jewels can have different factories and destinations. To ensure that the transportation of the jewels are not influenced by unknown factors, the company decided to buy all the roads that are needed and install special transportation facilities on each road. No roads can be used to transport two or more kinds of jewels, so every two kinds of jewels must follow two edge-disjoint paths from their own factories to destinations. Help the company to minimize the cost to buy the roads and install the facilities. Input The input consists of at most 10 test cases. Each case contains three integers n, m and k (1 ≤ n ≤ 16, 1 ≤ m ≤ 100, 1 ≤ k ≤ 5), the number of cities, the number of roads and the number of kinds of jewels. Each of the following m lines begins with two different integers a, b, and then followed by k integers ci (1 ≤ ci ≤ 1000), describing a directed road from city a to city b, with cost ci if you install facilities for transporting the i-th jewel. Cities are numbered 1 to n. Each of the last k lines describes one kind of jewel by two integers s and t, that is the city of factory and destination. The last test case is followed by three zeros, which should not be processed. Output For each test case, print the minimal cost in the first line (if there is no solution, print ‘-1’). If there is a solution, print k lines one for each kind of jewel. The first integer is the number of roads, then a list of roads. Roads are numbered 1 to m in the order they appear in the input. Sample Input 4 10 2 1 3 27 50 4 1 45 23 2 3 13 24 4 2 12 64 2 4 93 45 4 1 89 12 3 4 5 83 3 2 76 35 3 2 10 48 3 1 34 29 32 34 000 Sample Output 90 19 258