B'Doremy has an edge-weighted tree with n vertices whose weights are integers between 1 and 10^9 . She does frac{n(n+1)}{2} experiments on it. In each experiment, Doremy chooses vertices i and j such that j <= q i and connects them directly with an edge with weight 1 . Then, there is exactly one cycle (or self-loop when i=j ) in the graph. Doremy defines f(i,j) as the sum of lengths of shortest paths from every vertex to the cycle. Formally, let mathrm{dis}_{i,j}(x,y) be the length of the shortest path between vertex x and y when the edge (i,j) of weight 1 is added, and S_{i,j} be the set of vertices that are on the cycle when edge (i,j) is added. Then, f(i,j)= sum_{x=1}^{n} <= ft( min_{y in S_{i,j}} mathrm{dis}_{i,j}(x,y) right). Doremy writes down all values of f(i,j) such that 1 <= q j <= q i <= q n , then goes to sleep. However, after waking up, she finds that the tree has gone missing. Fortunately, the values of f(i,j) are still in her notebook, and she knows which i and j they belong to. Given the values of f(i,j) , can you help her restore the tree? It is guaranteed that at least one suitable tree exists. The first line of input contains a single integer n ( 2 <= n <= 2000 ) -- the number of vertices in the tree. The following n lines contain a lower-triangular matrix with i integers on the i -th line; the j -th integer on the i -th line is f(i,j) ( 0 <= f(i,j) <= 2 cdot 10^{15} ). It is guaranteed that there exists a tree whose weights are integers between 1 and 10^9 such that the values of f(i,j) of the tree match those given in the input. Print n-1 lines describing the tree. In the i -th line of the output, output three integers u_i , v_i , w_i ( 1 <= u_i,v_i <= n , 1 <= w_i <= 10^9 ), represen'...