Reconstructing a Tree from Endpoint Distances

Given an unrooted tree with $$n$$ nodes where each edge has a positive integer weight representing its length, the distance between any two nodes is the sum of weights along the unique path connecting them. For every node $$i$$ with $$2 \leq i \leq n-1$$, you are given its distance from node $$1$$ (denoted as $$d_{1,i}$$) and its distance from node $$n$$ (denoted as $$d_{n,i}$$). It is guaranteed that the input is consistent, meaning that for each such node $$i$$, $$d_{1,i} + d_{n,i}$$ is equal to a constant (namely, the distance between nodes $$1$$ and $$n$$). Using these distances, you are to reconstruct a tree that satisfies the given conditions.

A valid reconstruction is to assume that all the nodes lie on the unique simple path from node $$1$$ to node $$n$$. In this case, if we sort the nodes $$2,3,\ldots,n-1$$ by $$d_{1,i}$$ in increasing order, then the edge from node $$1$$ to the first node will have weight $$d_{1,i}$$ of the first node, the edge between any two consecutive nodes will have weight equal to the difference of their $$d_{1,i}$$ values, and finally the edge connecting the last node to node $$n$$ will have weight equal to its $$d_{n,i}$$. This construction satisfies $$d_{1,i}$$ and $$d_{n,i}$$ for every node on the path.

inputFormat

The first line contains a single integer $$n$$, the number of nodes in the tree.

Each of the following $$n-2$$ lines contains two space‐separated positive integers $$d_{1,i}$$ and $$d_{n,i}$$ (for $$i = 2,3,\ldots,n-1$$), which represent the distance from node $$1$$ to node $$i$$ and the distance from node $$n$$ to node $$i$$, respectively.

outputFormat

Output exactly $$n-1$$ lines. Each line should contain three space‐separated integers $$u$$, $$v$$, and $$w$$, indicating that there is an edge between node $$u$$ and node $$v$$ with weight $$w$$. The reconstructed tree must satisfy that for each node $$i$$ (with $$2 \le i \le n-1$$), the distance from node $$1$$ to node $$i$$ is $$d_{1,i}$$ and the distance from node $$n$$ to node $$i$$ is $$d_{n,i}$$.

sample

4
2 5
4 3

1 2 2
2 3 2
3 4 3