Problem Description

Rasuk has lost his tree.

This tree had vertices numbered with distinct integers from $1$ to the number of vertices, and each edge had an integer weight between $1$ and $10^9$.

The number of vertices is between $K$ and $1000$, and for $1 \leq i, j \leq K$, the distance between vertex $i$ and vertex $j$ is $D_{ij}$. Here, the distance between vertex $i$ and vertex $j$ refers to the sum of the weights of the edges on the simple path connecting vertex $i$ and vertex $j$.

From this information, output one possible tree that Rasuk had. Note that for the given input, it is guaranteed that at least one tree that satisfies the conditions exists.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output one possible tree that Rasuk had in the following format:

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

The graph formed by connecting vertex $a_i$ and vertex $b_i$ with an edge of weight $c_i$ is a tree that satisfies the conditions.

If multiple trees satisfy the conditions, any one of them can be output.

The value of $c_i$ must be an integer between $1$ and $10^9$.

Sample Input and Output

Sample Input #1

4
0 3 4 5
3 0 5 6
4 5 0 7
5 6 7 0

Sample Output #1

5
1 5 1
4 5 4
5 2 2
5 3 3

Sample Input #2

3
0 2 3
2 0 5
3 5 0

Sample Output #2

4
1 4 1
1 2 2
4 3 2

Sample Input #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

Sample Output #3

8
4 6 2
6 1 1
2 7 3
7 8 2
7 6 1
5 8 1
8 3 2

Notes/Hints

Constraints

• All inputs are integers.
• $2 \leq K \leq 300$
• $1 \leq D_{ij} \leq 10^9$ for $i \neq j$
• $ D_{ij} = D_{ji} $
• $ D_{ii} = 0 $
• There is at least one tree that satisfies the conditions of the problem.

Sample Explanation 1

For example, a tree like the one shown below satisfies the conditions.

见题面 Input 部分

见题面 Output 部分