Legends and Myths of Southern Butovo#4161
In the year 3141, Butovo has become an unusually tricky district, plagued not by danger, but by a curious challenge: mischievous robot pigeons have taken over the city squares! They play harmless pranks on anyone who tries to change direction at an intersection, making navigation quite a headache for the city residents.
Butovo is organized with avenues running north to south and streets running east to west. Each avenue intersects with each street at exactly one intersection. While moving quickly in a straight line along avenues or streets is smooth, turning at any intersection is an ordeal—because that's where the robot pigeons gather to confuse travelers.
To help citizens get around easily, the city council has decided to set up special guidance booths at certain intersections. At these booths, helpful guides can safely and cheerfully redirect travelers, making it possible to change direction without being sidetracked by robotic antics.
The council's budget, however, is limited this year because the mayor is funding a massive city garden project. So, the goal is to set up the minimum number of booths at the lowest total cost. For proper operation, booths must be placed so that residents can get from any intersection to any other, making turns only where these guidance booths are located.
The challenge doesn't end there: different parts of Butovo pose different construction costs for guidance booths. Each area has a center located at a specific intersection, and any other intersection belongs to the area whose center is nearest to it, measured in the unique Butovo distance: the minimal number of intermediate intersections required to travel from one to another, plus one. If several area centers are the same distance from a given intersection, then the constant gatherings of robot pigeons at that intersection make it impossible to place a booth there.
Your task is to determine the minimum cost to place booths, given Butovo's layout, so that travel is possible between any two intersections by turning only at intersections equipped with guidance booths.
The first line of input contains three numbers: , , and — the number of avenues, the number of streets, and the number of areas in Butovo, respectively (2 \leq N, M \leq 500, 1 \leq R \leq 1000). The next lines each contain three integers: the avenue number and street number of an area's center, and the cost of building a booth in that area. Avenues and streets are numbered starting from one, and all construction costs are positive and do not exceed one thousand. No two areas have overlapping centers.
On the first line of output, print two numbers: the number of intersections where booths should be built, and the minimum total construction cost found. In the next lines, provide descriptions of the intersections where booths are located: the avenue number and the street number at each intersection. If it's impossible to place the booths as required, print the single number -1.
Example 1