CF398C.Tree and Array

User ainta likes trees. This time he is going to make an undirected tree with $n$ vertices numbered by integers from $1$ to $n$ . The tree is weighted, so each edge of the tree will have some integer weight.

Also he has an array $t$ : $t[1],t[2],...,t[n]$ . At first all the elements of the array are initialized to $0$ . Then for each edge connecting vertices $u$ and $v$ ( u<v ) of the tree with weight $c$ , ainta adds value $c$ to the elements $t[u],t[u+1],...,t[v-1],t[v]$ of array $t$ .

Let's assume that $d(u,v)$ is the total weight of edges on the shortest path between vertex $u$ and vertex $v$ . User ainta calls a pair of integers $x,y$ ( 1<=x<y<=n ) good if and only if $d(x,y)=t[x]+t[x+1]+...+t[y-1]+t[y]$ .

User ainta wants to make at least good pairs, but he couldn't make a proper tree. Help ainta to find such a tree.

The first line contains a single integer $n$ ( $5<=n<=10^{5}$ ).

Print $n-1$ lines containing the description of the edges. The $i$ -th line should contain three space-separated integers $u_{i},v_{i},c_{i}$ ( 1<=u_{i}<v_{i}<=n; 1<=c_{i}<=10^{5} ) — two vertices connected by the edge, and the weight of the edge.

Next print lines containing the good pairs. The $k$ -th line should contain two space-separated integers $x_{k}$ and $y_{k}$ ( 1<=x_{k}<y_{k}<=n ). Of course, $x_{k},y_{k}$ must be a good pair. All pairs should be distinct — that is, for all $j,k$ , $x_{j}≠x_{k}$ or $y_{j}≠y_{k}$ must be satisfied.

If there are many correct solutions, print any of them.

$⌊x⌋$ is the largest integer not greater than $x$ .

You can find the definition of a tree by the following link: http://en.wikipedia.org/wiki/Tree_(graph_theory)

You can also find the definition of the shortest path by the following link: http://en.wikipedia.org/wiki/Shortest_path_problem

The tree and the array $t$ in the sample output look like this: