VIII Olimpiada Informatyczna 2000/2001

Task: WYS

Author: Wojciech Guzicki

II stage contest, the first day 
On an island of the shape of a convex polygon with 2n sides, there are situated 2n2 countries. Each country has a territory in the shape of triangle, which vertices are placed at the vertices of the polygon. There are no countries which border exactly with two different countries (therefore, each country borders with only one or three countries). It implies, that there are exactly n countries bordering with one country only (these are seaside countries) and n2 countries bordering with three neighbours (these are inland countries). Seaside countries are numbered from 1 to n, inland countries have numbers from n+1 to 2n2. When we travel from one country to another, we are obliged to pay a charge on the border. Charges may be different on different borders, but crossing a border costs the same amount of money in both directions.
For each two countries i,j from n seaside countries, it is known how much one has to pay traveling from i to j, assuming that the land route from one country to the other through the least number of borders was chosen. The task is to find all the charges on the island. For each seaside country there should be given the number of neighbouring country and the charge on the border. Moreover, for each n2 inland countries there should be given numbers of three neighbouring countries and the charges on borders.
Write a program which:
In the first line of the text file WYS.IN there is one positive integer n, 4<=n<=100. This is the number of seaside countries. In each of the following n lines there are n nonnegative integers separated by single spaces. The number d_{i,j}, on the jth position in the ith line, is equal to the sum of border charges on the route (through the least number of borders) from the ith country to the jth country. We assume that the charge on each border is an integer from the interval [1..100]. Of course, d_{i,j}=d_{j,i} and d_{i,i}=0.
In each of the first n lines of the text file WYS.OUT there should be written two integers separated by a single space. The first number in the ith line should be the number of the country, which borders with the country number i. The second number is the charge on the border between these two countries. In each of the following n2 lines there should be written six integers separated by single spaces. In the line number i, n+1<=i<=2n1, the first  number of the first country bordering with the ith country, the second  the charge on their border, the third  number of the second country bordering with the ith country, the forth  the charge on the second border, the fifth  the number of the third country bordering with the ith country, the sixth  the charge on the third border. Inland countries are numbered from n+1 to 2n2.
For the input file WYS.IN:
7 0 8 10 8 13 11 14 8 0 8 10 11 5 12 10 8 0 12 5 11 6 8 10 12 0 15 13 16 13 11 5 15 0 14 3 11 5 11 13 14 0 15 14 12 6 16 3 15 0
the correct answer is the output file WYS.OUT (see the picture below):
12 3 10 1 9 1 12 5 8 1 10 4 8 2 5 1 7 2 9 3 3 1 8 3 11 4 2 1 6 4 11 2 9 4 10 2 12 2 1 3 4 5 11 2 