AT_cpsco2019_s4_f Lost Tree
题目描述
拉斯克君曾经拥有一棵美丽的树，不过，他现在把它弄丢了。
这棵树的每个顶点都有一个从 $1$ 到顶点总数之间的独特编号，每条边也都有一个从 $1$ 到 $10^9$ 间的整数权重。
树的顶点数在 $K$ 和 $1000$ 之间。对于任意两个顶点 $i$ 和 $j$（$1 \leq i, j \leq K$），它们之间的距离用 $D_{ij}$ 表示。在这里，顶点间的距离是指连接这两个顶点的简单路径上所有边的权重之和。
根据这些给定的信息，请输出一种可能的树结构，该树是拉斯克君遗失的树。题目保证，对于提供的输入，总可以找到至少一种符合条件的树。
输入格式
输入以如下格式呈现：
> $K$ $D_{11}$ $D_{12}$ $\ldots$ $D_{1K}$ $D_{21}$ $D_{22}$ $\ldots$ $D_{2K}$ : $D_{K1}$ $D_{K2}$ $\ldots$ $D_{KK}$
输出格式
请以如下格式输出一种符合条件的树：
> $N$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ : $a_{N-1}$ $b_{N-1}$ $c_{N-1}$
其中，$N$ 表示顶点数，$a_i$ 和 $b_i$ 是通过一条权重为 $c_i$ 的边直接相连的顶点，这个数据描述了一棵符合要求的树。
如果有多棵符合条件的树，输出其中任意一棵即可。
注意，边的权重 $c_i$ 必须是 $1$ 到 $10^9$ 之间的整数。
说明/提示
- 输入的所有数值均为整数。
- $2 \leq K \leq 300$
- 对于 $i \neq j$ 的情况，$1 \leq D_{ij} \leq 10^9$
- 距离满足对称性：$D_{ij} = D_{ji}$
- 每个顶点到自身的距离为零：$D_{ii} = 0$
- **题目确保至少存在一棵满足条件的树。**
### 样例解释 1
例如，下图所示的树符合条件：
### 样例解释 2
例如，下图所示的树符合条件：
**本翻译由 AI 自动生成**