问题描述

Lasku拥有一颗树，但不小心把它丢了。

这棵树上的每个顶点都被标记了 $1$ 到 $K$ 之间的不同整数，并且每条边上都有一个 $1$ 到 $10^9$ 之间的整数作为权重。

顶点的数量在 $K$ 到 $1000$ 之间，在 $1 \leq i, j \leq K$ 的条件下，顶点 $i$ 和顶点 $j$ 之间的距离为 $D_{ij}$。其中，两个顶点之间的距离是指它们之间的简单路径上所有边的权重之和。

请根据这些信息输出一棵可能是Lasku所拥有的树。请注意，对于给定输入，至少存在一棵满足条件的树。

约束条件

• 输入是整数。
• $2 \leq K \leq 300$
• 当 $i < j$ 时，$1 \leq D_{ij} \leq 10^9$
• $D_{ij}=D_{ji}$
• $D_{ii}=0$
• 至少存在一棵满足问题描述条件的树。

输入

输入从标准输入读取，并具有以下格式。

$K$ $D_{11}$ $D_{12}$ $\ldots$ $D_{1K}$ $D_{21}$ $D_{22}$ $\ldots$ $D_{2K}$ : $D_{K1}$ $D_{K2}$ $\ldots$ $D_{KK}$

输出

请以以下格式输出一棵可能是Lasku所拥有的树。

$N$ $a_1$ $b_1$ $c_1$ $a_2$ $b_2$ $c_2$ : $a_{N-1}$ $b_{N-1}$ $c_{N-1}$

其中，顶点数量为 $N$，通过权重为 $c_i$ 的边连接顶点 $a_i$ 和顶点 $b_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