配点 : 800 点
有关输出树边权重的问题陈述已得到纠正。对于给您带来的任何不便,我们深表歉意。 (12:06)問題文
腊斯克有一棵树,但他失去了它。
这棵树有 1 每条边都用不同的整数进行编号,大于或等于顶点数,小于或等于顶点数。 1 以上 10^9 确定以下整数权重。
顶点数为 K 以上 1000 小于或等于 对于1 \leq i, j \leq K ,顶点 i 和边 j 的距离是 这是 D_{ij} 。然而,顶点 i 和边 j 距离是顶点 它是连接 i 和边 j 的简单路径中包含的边的权重之和。
根据这些信息,请输出一棵你认为腊斯克拥有的树。请注意,对于此问题中给出的任何输入,保证至少有一棵树符合条件。
制約
- 所有输入均为整数。
- 2 \leq K \leq 300
- i < j 到 1 \leq D_{ij} \leq 10^9
- D_{ij}=D_{ji}
- D_{ii}=0
- 满足问题陈述条件的树至少是 1 有两个。
入力
输入是按以下格式从标准输入给出的。
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 的整数。
入力例 1
4 0 3 4 5 3 0 5 6 4 5 0 7 5 6 7 0
出力例 1
5 1 5 1 4 5 4 5 2 2 5 3 3
例如,如下所示的树满足条件。
入力例 2
3 0 2 3 2 0 5 3 5 0
出力例 2
4 1 4 1 1 2 2 4 3 2
例如,如下所示的树满足条件。
入力例 3
5 0 5 6 3 5 5 0 7 6 6 6 7 0 7 3 3 6 7 0 6 5 6 3 6 0
出力例 3
8 4 6 2 6 1 1 2 7 3 7 8 2 7 6 1 5 8 1 8 3 2