Island

An island has the shape of a convex polygon with $2n$ sides. It is divided into $2n-2$ countries, each shaped like a triangle whose three corners are vertices of the polygon; that is, the polygon is cut into triangles by non-crossing diagonals.

No country borders exactly two other countries: every country borders either one country or three countries. Consequently there are exactly $n$ countries that border a single neighbour (the seaside countries) and $n-2$ countries that border three neighbours (the inland countries). The seaside countries are numbered from $1$ to $n$, and the inland countries from $n+1$ to $2n-2$.

Crossing a border costs a toll. Different borders may cost different amounts, but crossing a given border costs the same in both directions. Each toll is an integer between $1$ and $100$.

For every pair of seaside countries $i$ and $j$ you are told the total toll paid when travelling from $i$ to $j$ along the route that crosses the fewest borders. (Because the countries form a tree of borders, this route is unique.) From this information, reconstruct every border and its toll: for each country, find its neighbours and the toll on each shared border.

The first line contains one integer $n$ ($4 \le n \le 100$), the number of seaside countries.

Each of the next $n$ lines contains $n$ non-negative integers separated by single spaces. The $j$-th integer on the $i$-th line, $d_{i,j}$, is the total toll on the route (crossing the fewest borders) from seaside country $i$ to seaside country $j$. The data satisfy $d_{i,j}=d_{j,i}$ and $d_{i,i}=0$, and are guaranteed to be consistent with some island whose every border toll is an integer in $[1,100]$.

Print $2n-2$ lines describing the borders.

On each of the first $n$ lines, describe one seaside country: line $i$ (for $1 \le i \le n$) contains two integers, the number of the country that borders seaside country $i$ and the toll on that border.

On each of the next $n-2$ lines, describe one inland country: the line for inland country $c$ (for $n+1 \le c \le 2n-2$) contains six integers, listing its three neighbours in increasing order of neighbour number, each neighbour's number followed by the toll on the shared border.

Number the inland countries deterministically so that the answer is unique. Assign the numbers $n+1, n+2, \ldots, 2n-2$ by a depth-first traversal of the border tree that starts at the inland country adjacent to seaside country $1$: give the next unused number to each inland country the moment the traversal first reaches it, and from each inland country continue into its not-yet-numbered inland neighbours in increasing order of the smallest seaside-country number reachable through that border (without passing back through the current country).

The figure below illustrates an island of this kind: the seaside countries around the coast, the inland countries in the interior, and the borders (with their tolls) between them.