Absurdistan Roads#7013
The people of Absurdistan learned how to build roads only last year. After this discovery, each city decided to build exactly one road connecting it to another city. Each newly built road can be used in both directions.
Absurdistan is full of surprising coincidences. It took all cities exactly one year to build their roads. Even more surprisingly, after all the roads were built, it was possible to travel from every city to every other city using only the newly built roads.
You bought a tourist guide that does not contain a map of the country with the new roads. Instead, it contains a large table with the shortest distances between every pair of cities using the newly built roads.
You would like to determine which pairs of cities are connected by roads and what the lengths of those roads are. In other words, you want to reconstruct the map of the newly built roads from the table of shortest distances.
For each test case:
A line containing an integer n~(2 \le n \le 2000) — the number of cities and roads.
lines, each containing integers. The -th integer on the -th line is the shortest distance from city to city using the newly built roads. The distance between any two distinct cities is positive and at most 10^6. The distance from city to itself is always , and the distance from city to city is the same as the distance from city to city .
For each test case, print lines, each containing three integers , , and , indicating that there is a road between cities and b~(1 \le a, b \le n) with length c~(1 \le c \le 10^6), where a \ne b.
If multiple solutions exist, you may print any one of them, and the roads may be printed in any order. At least one valid solution is guaranteed to exist.
Print a blank line between every two consecutive test cases.
Example 1