Graph Reconstruction

There is a connected weighted undirected graph with N vertices and M edges. The vertices are numbered from 1 to N.

The actual edges of the graph are unknown, but the shortest distance between every pair of distinct vertices is given. Construct any graph whose shortest distances exactly match the given data.

The first line contains two natural numbers N and M. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1,000)

The next N-1 lines contain the shortest distance data. The i-th of these lines gives the shortest distances from vertex i to vertices i+1, i+2, ..., N, in that order, separated by spaces.

Every shortest distance is a natural number not greater than 500.

If no graph can exactly match the given shortest distances, print 0 on the first line.

Otherwise, print 1 on the first line, followed by M lines describing the edges. Each edge must be printed as a b c, meaning that there is an edge of weight c between vertices a and b. The vertices a and b must be different, and c must be a natural number not greater than 500.