Dedication#1720
To become an adult gnome, one must pass through a frightening maze. The maze is so confusing and dangerous that gnomes can only enter it in pairs. Each pair must consist of a boy and a girl. Because there may be a different number of boys and girls, some gnomes will have to go through the maze several times (the important thing is that every gnome passes it at least once).
For every pair of boy and girl who are friends, the adult gnomes know how much time it will take this pair to find the exit from the maze. Help the gnomes to get all the children through the maze in the minimum possible total time.
The first line of the input contains two integers and — the numbers of boys and girls among the gnomes, respectively (1 \leq n, m \leq 100). The second line contains the integer — the number of pairs that can be sent together (1 \leq r \leq 1000). The following lines each contain three integers: a_i, b_i and c_i. These values mean that boy number a_i can go through the maze with girl number b_i, and they will take c_i seconds to pass it together (1 \leq c_i \leq 1000). It is guaranteed that every gnome has at least one friend to go into the maze with.
The first line of the output should print the minimum possible total time required for all the children to complete the initiation. On the second line, print — the number of pairs that need to be sent. The third line should contain integers — the indices of these pairs as they appear in the input.
Example 1