그래프 복원

정점이 N개이고 간선이 M개인 연결된 가중 무향 그래프가 있다. 정점은 1부터 N까지 번호가 붙어 있다.

그래프의 실제 간선 정보는 알려져 있지 않지만, 서로 다른 모든 두 정점 사이의 최단 거리는 주어진다. 주어진 최단 거리 정보와 일치하는 그래프를 하나 구성하라.

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1,000)

다음 N-1개의 줄에는 최단 거리 정보가 주어진다. 그중 i번째 줄에는 정점 i에서 정점 i+1, i+2, ..., N까지의 최단 거리가 이 순서대로 공백으로 구분되어 주어진다.

모든 최단 거리는 500 이하의 자연수이다.

주어진 최단 거리와 정확히 일치하는 그래프를 구성할 수 없으면 첫째 줄에 0을 출력한다.

구성할 수 있으면 첫째 줄에 1을 출력하고, 이어서 M개의 줄에 간선을 하나씩 출력한다. 각 줄은 a b c 형식이며, 정점 a와 b를 잇는 가중치 c인 간선을 뜻한다. a와 b는 서로 달라야 하고, c는 500 이하의 자연수여야 한다.