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.

Doremy 有一棵含 $n$ 个顶点的边权树，各边权值为 $1$ 到 $10^9$ 之间的整数。她在该树上进行了 $\frac{n(n+1)}{2}$ 次实验。

每次实验中，Doremy 选择两个顶点 $i$ 和 $j$（满足 $j \leq i$），并用一条权值为 $1$ 的边直接连接它们。此时图中恰好形成一个环（当 $i = j$ 时为自环）。Doremy 将 $f(i,j)$ 定义为：所有顶点到该环的最短路径长度之和。

形式化地，设 $\mathrm{dis}_{i,j}(x,y)$ 表示在添加权值为 $1$ 的边 $(i,j)$ 后，顶点 $x$ 与 $y$ 之间的最短路径长度；设 $S_{i,j}$ 为添加边 $(i,j)$ 后构成的环上的顶点集合。则：

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

Doremy 将所有满足 $1 \leq j \leq i \leq n$ 的 $f(i,j)$ 值记录下来，然后入睡。然而醒来后，她发现原树已丢失。幸运的是，她的笔记本中仍保留着所有 $f(i,j)$ 的值，并且她清楚每个值对应的 $i$ 和 $j$。已知这些 $f(i,j)$ 的值，你能帮她恢复出原来的树吗？

题目保证至少存在一棵满足条件的树。

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.

输入的第一行包含一个整数 $n$（$2 \le n \le 2000$），表示树中顶点的数量。

接下来的 $n$ 行包含一个下三角矩阵，其中第 $i$ 行有 $i$ 个整数；第 $i$ 行第 $j$ 个整数为 $f(i,j)$（$0 \le f(i,j) \le 2\cdot 10^{15}$）。

保证存在一棵树，其边权均为 $1$ 到 $10^9$ 之间的整数，且该树对应的 $f(i,j)$ 值与输入中给出的值完全一致。

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.

输出 $n-1$ 行，描述该树。在输出的第 $i$ 行中，输出三个整数 $u_i$、$v_i$、$w_i$（其中 $1 \le u_i,v_i \le n$，$1 \le w_i \le 10^9$），表示一条权重为 $w_i$ 的边 $(u_i,v_i)$。

若存在多个合法答案，输出任意一个即可。

所有边必须构成一棵树，且所有 $f(i,j)$ 的值必须与输入中给出的值完全一致。

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.

在第一个测试用例中，下图从左到右、从上到下依次展示了分别连接边 $(1,1)$、$(1,2)$、$(1,3)$、$(2,2)$、$(2,3)$、$(3,3)$ 时对应的图。图中黄色标记的节点位于环上。