31320번 - Colonization 스페셜 저지다국어

문제

The yoghurt bottle is populated with $N$ bacteria. But bacteria want company, so they form colonies, and this happens in the following way. Initially each bacterium is a colony consisting of itself. While there are at least two colonies in the yoghurt, two nearest colonies are chosen at each step and merged together.

Initially for each pair of bacteria $u$ and $v$ the distance $d_{u,v}$ between them is known. The distance for the colonies $G$ and $H$ is calculated as the average distance between all pairs of bacteria: $$ \frac{ 1 }{|G| \cdot |H|} \sum_{u \in G} \sum_{v \in H} d_{u, v} $$

Bacteria aren't very particular when it comes to accuracy --- you cannot expect too much from single-cell organisms, anyway. So when there are several pairs of colonies with the distance within 10ドル^{-6}$ of the minimal, then any of these pairs can be selected for merging at this step.

You are to model the colony merging process and find one of the possible scenarios.

입력

The first line of the input file contains an integer $N$ -- the number of bacteria (2ドル \leq N \leq 2014$).

The following $N$ lines contain the description of the distance matrix $(d_{i,j})$. Each line contains $N$ characters. The character $d_{i,j}$ in the $j$-th position of the $i$-th line specifies the distance between the $i$-th and $j$-th bacteria.

It is guaranteed that $d_{i,i} = 0,ドル $d_{i, j} = d_{j, i},ドル 0ドル \leq d_{i, j} \leq 9$ for all $i,ドル $j$ = 1,ドル \ldots, N$.

출력

Assign numbers to each initial colony, from 1ドル$ to $N$. The colony obtained on the $i$-th step, $i = 1, \ldots, N-1,ドル will have the number $N + i$.

The input file must contain $N-1$ lines. The $i$-th line must contain three numbers: the numbers of colonies merged on the $i$-th step, and the distance between them with an absolute or relative error not greater than 10ドル^{-6}$ (1ドル \le i \le N-1$).

제한

힌트