그래프 구성하기

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

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

그러한 그래프가 존재하는지 판별하고, 존재한다면 그중 아무거나 하나를 출력하세요.

첫 번째 줄에 정점의 개수 $N$이 주어집니다. 이어지는 $N$개 줄 중 $i$번째 줄에는 공백으로 구분된 정수 $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 \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$)
• 같은 쌍의 정점을 잇는 간선은 최대 하나여야 한다.