Dedication
To become an adult gnome, each must navigate a daunting maze. The maze is so complex and perilous that gnomes must traverse it in pairs. Each pair should consist of one boy and one girl. Given that the number of boys and girls may differ, some gnomes will need to go through the maze more than once, but every gnome must complete it at least once.
For each boy-girl pair who are friends, the adult gnomes know how long it will take them to exit the maze. Your task is to help them ensure all the children pass through the maze in the shortest possible time.
Input
The first line of the input contains two integers, n and m, representing the number of boys and girls among the gnomes, respectively (1 ≤ n, m ≤ 100). The second line contains the integer r, which is the number of potential pairs that can be sent together (1 ≤ r ≤ 1000). The following r lines each contain three integers: a_i, b_i, and c_i. These indicate that the boy numbered a_i can enter the maze with the girl numbered b_i, and they will take c_i seconds to complete it (1 ≤ c_i ≤ 1000). It is guaranteed that every gnome has at least one friend with whom they can enter the maze.
Output
On the first line of the output, print the minimum total time required for the initiation. On the second line, print k, the number of pairs that need to be sent into the maze. The third line should list k integers, which are the indices of these pairs as they appear in the input.