给你一个 $n \times n$ 的方阵 $D$。你的任务是构造一个包含 $n$ 个顶点的无向连通图，满足以下条件。每个顶点的编号为 $1$ 到 $n$，你可以根据需要为每条边分配正整数边权。

• 对于所有顶点对 $(u, v)$，顶点 $u$ 和 $v$ 之间的最短路径长度必须等于 $D_{u,v}$。
• 边权的总和必须最小。

判断是否存在满足上述条件的图，如果存在，输出任意一个满足条件的图。

输入格式

第一行包含一个整数 $n$，表示顶点数（$2 \leq n \leq 300$）。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $D_{i,1}, D_{i,2}, \ldots, D_{i,n}$（对于 $i \ne j$，有 $1 \leq D_{i, j} \leq 10^9$；$D_{i, j} = D_{j, i}$；$D_{i, i} = 0$）。

输出格式

如果不存在满足条件的图，输出 $-1$。

如果存在满足条件的图：

• 第一行输出一个整数 $m$，表示边数。
• 接下来的 $m$ 行中，第 $i$ 行输出三个整数：$u_i$、$v_i$ 和 $c_i$。这些整数表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$，且其边权为 $c_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$，$1 \leq c_i \leq 10^9$）。任意两点之间最多只能有一条边。
• 如果有多个最优解，输出其中任意一个。

样例

输入样例 1

3
0 1 2
1 0 3
2 3 0

输出样例 1

2
1 2 1
1 3 2

输入样例 2

3
0 1 3
1 0 1
3 1 0

输出样例 2

-1