CF1764F.Doremy's Experimental Tree

Doremy has an edge-weighted tree with $n$ vertices whose weights are integers between $1$ and $10^9$ . She does $\frac{n(n+1)}{2}$ experiments on it.

In each experiment, Doremy chooses vertices $i$ and $j$ such that $j \leq i$ and connects them directly with an edge with weight $1$ . Then, there is exactly one cycle (or self-loop when $i=j$ ) in the graph. Doremy defines $f(i,j)$ as the sum of lengths of shortest paths from every vertex to the cycle.

Formally, let $\mathrm{dis}_{i,j}(x,y)$ be the length of the shortest path between vertex $x$ and $y$ when the edge $(i,j)$ of weight $1$ is added, and $S_{i,j}$ be the set of vertices that are on the cycle when edge $(i,j)$ is added. Then,

$$f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right).$$

Doremy writes down all values of $f(i,j)$ such that $1 \leq j \leq i \leq n$ , then goes to sleep. However, after waking up, she finds that the tree has gone missing. Fortunately, the values of $f(i,j)$ are still in her notebook, and she knows which $i$ and $j$ they belong to. Given the values of $f(i,j)$, can you help her restore the tree?

It is guaranteed that at least one suitable tree exists.

The first line of input contains a single integer $n$ ($2 \le n \le 2000$) — the number of vertices in the tree.

The following $n$ lines contain a lower-triangular matrix with $i$ integers on the $i$ -th line; the $j$ -th integer on the $i$ -th line is $f(i,j)$ ( $0 \le f(i,j) \le 2\cdot 10^{15}$ ).

It is guaranteed that there exists a tree whose weights are integers between $1$ and $10^9$ such that the values of $f(i,j)$ of the tree match those given in the input.

Print $n-1$ lines describing the tree. In the $i$ -th line of the output, output three integers $u_i$ , $v_i$ , $w_i$ ( $1 \le u_i,v_i \le n$ , $1 \le w_i \le 10^9$ ), representing an edge $(u_i,v_i)$ whose weight is $w_i$ .

If there are multiple answers, you may output any.

All edges must form a tree and all values of $f(i,j)$ must match those given in the input.

In the first test case, the picture below, from left to right, from top to bottom, shows the graph when pairs $(1,1)$ , $(1,2)$ , $(1,3)$ , $(2,2)$ , $(2,3)$ , $(3,3)$ are connected with an edge, respectively. The nodes colored yellow are on the cycle.