You are given an $n \times n$ square matrix $D$. Your task is to construct an undirected connected graph with $n$ vertices that fulfills the following conditions. Each vertex is numbered from $1$ to $n$, and you may assign positive integer weights to each edge as desired.

• For all pairs of vertices $(u, v)$, the length of the shortest path between $u$ and $v$ must be equal to $D_{u,v}$.
• The total sum of edge weights must be minimized.

Determine whether such a graph exists, and if so, print any graph that satisfies these conditions.

Input

The first line contains an integer $n$, the number of vertices ($2 \leq n \leq 300$).

The $i$-th of the next $n$ lines contains $n$ integers $D_{i,1}, D_{i,2}, \ldots, D_{i,n}$ ($1 \leq D_{i, j} \leq 10^9$ for $i \ne j$, $D_{i, j} = D_{j, i}$, $D_{i, i} = 0$).

Output

If no graph satisfies the conditions, print $-1$.

If there exists a graph that satisfies the conditions:

• On the first line, print an integer $m$, the number of edges.
• On the $i$-th of the next $m$ lines, print three integers: $u_i$, $v_i$, and $c_i$. These integers mean that the $i$-th edge connects vertices $u_i$ and $v_i$, and its weight is $c_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq c_i \leq 10^9$). There should be at most one edge between each pair of vertices.
• If there are several optimal answers, print any one of them.

Examples

Input 1

3
0 1 2
1 0 3
2 3 0

Output 1

2
1 2 1
1 3 2

Input 2

3
0 1 3
1 0 1
3 1 0

Output 2

-1