Với đồ thị vô hướng đơn có trọng số $G$ gồm $N$ đỉnh từ $1$ đến $N$ và $M$ cạnh, ta định nghĩa điểm rừng như sau:

1. Gọi $F_1, F_2, F_3, \ldots, F_M$ lần lượt là các đồ thị gồm $N$ đỉnh từ $1$ đến $N$ và không có cạnh nào.
2. Gọi các cạnh của $G$ được sắp xếp theo trọng số tăng dần là $e_1, e_2, \ldots, e_M$. Với $i=1, 2, \ldots, M$, lần lượt thực hiện thao tác sau:
   • Tìm số nguyên dương $j$ nhỏ nhất sao cho khi thêm $e_i$ vào $F_j$ thì không tạo thành chu trình, rồi thêm $e_i$ vào $F_j$. Ở đây, thêm $e_i$ nghĩa là nếu $e_i$ có hai đầu mút là $u_i$ và $v_i$ thì ta thêm vào $F_j$ một cạnh nối đỉnh $u_i$ với đỉnh $v_i$.
3. Gọi $i$ lớn nhất sao cho $F_i$ có ít nhất một cạnh là điểm rừng của đồ thị $G$.

Bạn được giao nhiệm vụ sinh ra một đồ thị $G$ có điểm rừng chính xác bằng $k$ (với $k$ là số nguyên dương) và có nhiều nhất $2024$ đỉnh.

Đối với bạn, bài toán này quá dễ nên bạn thấy thú vị hơn khi tìm một đồ thị $G$ thỏa mãn các điều kiện bổ sung sau:

• Gọi $N$ là số đỉnh của $G$, thì số cạnh là $(2N-2)$.
• Có thể tô $(N-1)$ cạnh của $G$ màu đỏ và $(N-1)$ cạnh còn lại màu xanh sao cho chỉ giữ lại các cạnh đỏ thì được một cây, và chỉ giữ lại các cạnh xanh cũng được một cây.

Cho $k$, hãy tìm và in ra một đồ thị $G$ thỏa mãn các điều kiện.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $k$. ($2 \le k \le 12$)

Dữ liệu ra

Dòng đầu tiên in ra số đỉnh $N$ của đồ thị $G$. ($2 \le N \le 2024$)

$ (2N-2)$ dòng tiếp theo, dòng thứ $i$ in ra ba số nguyên $a_i, b_i, c_i$ cách nhau bởi dấu cách. ($1 \le a_i, b_i \le N$; $a_i \neq b_i$; $1 \le c_i \le 10^9$) Điều này thể hiện có một cạnh trọng số $c_i$ nối đỉnh $a_i$ và đỉnh $b_i$.

Đồ thị $G$ phải thỏa mãn các điều kiện sau:

• Tất cả các cạnh đều có trọng số phân biệt, tức là các $c_i$ đôi một khác nhau.
• $N-1$ cạnh đầu tiên được in ra tạo thành một cây. Tương tự, $N-1$ cạnh tiếp theo cũng tạo thành một cây.
• Không tồn tại cặp đỉnh nào được nối trực tiếp bởi nhiều hơn một cạnh.
• Điểm rừng của $G$ là $k$.

Ví dụ

Dữ liệu vào 1

3

Dữ liệu ra 1

5
1 2 8
2 3 1
3 4 2
4 5 5
1 3 6
3 5 4
5 2 7
2 4 3

Ghi chú

Dưới đây là một ví dụ về đáp án đúng cho $k=3$.

Đồ thị trên gồm hai cây không trùng nhau như có thể thấy trong hình dưới đây.

Tính điểm rừng ta được $3$ như sau. Các cạnh đỏ thuộc $F_1$, cạnh xanh thuộc $F_2$, cạnh xanh lục thuộc $F_3$.