Construct a Graph

$N\times N$ 크기의 행렬 $D$가 있다. 당신은 정점이 $N$개이고 아래 조건들을 만족하는 무방향 연결 그래프를 구성해야 한다. 각 정점은 $1$부터 $N$까지 번호가 매겨져 있으며, 각 간선에는 양의 정수 가중치를 원하는 대로 부여할 수 있다.

• 모든 정점 쌍 $(u,v)$에 대해, $u$와 $v$ 사이의 최단 경로의 길이는 $D_{u,v}$이다.
• 모든 간선의 가중치의 합은 가능한 최소여야 한다.

조건을 만족하는 그래프가 존재하는지 판별하고, 있다면 그 중 아무거나 하나를 출력하라.

첫 번째 줄에 정점의 개수를 나타내는 정수 $N$이 주어진다.

다음 $N$개 줄 중 $i$번째 줄에는 $N$개의 정수 $D_{i,1},D_{i,2},\ldots ,D_{i,N}$이 공백으로 구분되어 주어진다.

문제의 조건을 만족하는 그래프가 존재하지 않는다면, $-1$을 출력한다.

조건을 만족하는 그래프가 존재한다면,

• 첫 번째 줄에 간선의 개수를 나타내는 정수 $M$을 출력한다.
• 다음 $M$개 줄 중 $i$번째 줄에 세 정수 $u_i$, $v_i$, $c_i$를 공백으로 구분하여 출력한다. 이것은 $i$번 간선이 두 정점 $u_i$와 $v_i$를 잇고 가중치가 $c_i$라는 것을 나타낸다.
• 같은 쌍의 정점을 연결하는 간선은 최대 하나여야 하고, 각 간선의 가중치는 $10^9$ 이하여야 한다.

• $2\leq N\leq 300$
• $D_{i,i}=0$ ($1\le i\le N$)
• $1\leq D_{i,j}=D_{j,i}\leq 10^9$ ($1\le i<j\le N$)
• $1\leq u_i,v_i\leq N$ ($1\le i\le M$)
• $u_i\neq v_i$ ($1\le i\le M$)
• $1\leq c_i\leq 10^9$ ($1\le i\le M$)
• 같은 쌍의 정점을 연결하는 간선은 최대 하나여야 한다.