Construct a Graph

You are given an $N\times N$ matrix $D$. Build an undirected connected graph with $N$ vertices that satisfies the conditions below. Vertices are numbered from 1 to $N$, and each edge can be given any positive integer weight.

• For every pair of vertices $(u,v)$, the length of the shortest path between $u$ and $v$ is $D_{u,v}$.
• The sum of all edge weights must be as small as possible.

Determine whether such a graph exists. If it does, print any one of them.

The first line contains the integer $N$, the number of vertices. Each of the next $N$ lines contains $N$ integers separated by spaces. The $i$-th of these lines contains $D_{i,1}, D_{i,2}, \ldots, D_{i,N}$.

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

If such a graph exists, print the number of edges $M$ on the first line. On each of the next $M$ lines, print three integers $u_i$, $v_i$, $c_i$ separated by spaces. This means that edge $i$ connects vertices $u_i$ and $v_i$ and has weight $c_i$.

At most one edge may connect any pair of vertices, and each edge weight must be at most $10^9$.

• $2 \le N \le 300$
• $D_{i,i}=0$ ($1 \le i \le N$)
• $1 \le D_{i,j}=D_{j,i} \le 10^9$ ($1 \le i < j \le N$)
• $1 \le u_i, v_i \le N$ ($1 \le i \le M$)
• $u_i \neq v_i$ ($1 \le i \le M$)
• $1 \le c_i \le 10^9$ ($1 \le i \le M$)
• At most one edge may connect any pair of vertices.