Legends and Myths of Southern Butovo
In the year 3141, Butovo has become an extremely dangerous district, teeming with murderers and other criminals. It's so perilous that even traveling in a tank feels unsafe!
To remind you, Butovo is structured with N avenues running north to south and M streets running east to west. Each avenue intersects with each street at exactly one intersection. While moving quickly along an avenue or street is safe, making a turn is very risky because it requires slowing down, which is when local gangs attack.
The Butovo police department has decided to improve the situation slightly. They plan to establish several posts at certain intersections, allowing residents to turn safely without fear of attack. The police are equipped with the latest "Musket-1812" rifles and can protect every law-abiding citizen's honor and dignity.
However, the department's budget is tight this year because the head of the department is building a new elite mansion. Therefore, they aim to minimize spending on new posts. To maintain order, posts must be placed so that it's possible to travel from any intersection to any other, turning only at these specially equipped posts. Failure to do so will result in an inspection and potential dismissals.
Butovo's challenges don't end there. Some areas are more dangerous, and posts in these areas are more costly. Each area has a center located near a specific intersection. Any other intersection belongs to the area whose center is closest. The distance between intersections is measured using the Butovo distance: the minimum number of intermediate intersections needed to travel from one to another, plus one. If multiple area centers are equidistant from an intersection, constant clashes between authorities make it impossible to build a post there.
Your task is to determine the minimum cost of building posts, given Butovo's layout, so that safe travel is possible between any two intersections.
Input
The first line of the input contains three numbers: N, M, and R—the number of avenues, streets, and areas in Butovo, respectively (2 ≤ N, M ≤ 500, 1 ≤ R ≤ 1000). The next R lines each contain three integers: the avenue number, the street number where the area's center is located, and the cost of building a post in that area. Avenues and streets are numbered starting from one, and construction costs are positive and do not exceed one thousand. No two areas have overlapping centers.
Output
On the first line of the output, print two numbers: the number of intersections K where posts should be built, and the minimum total construction cost found. In the next K lines, provide descriptions of the intersections where posts are located: the avenue number and the street number at each intersection. If it's impossible to place the posts as required, print the single number -1.