Cho đồ thị hai phía ~G=\left(X \cup Y, E \right)~; các đỉnh của ~X~ ký hiệu là ~x_1, x_2, ..., x_n~, các đỉnh của ~Y~ ký hiệu là ~y_1, y_2, ..., y_n~. Mỗi cạnh của ~G~ được gán một trọng số không âm. Một bộ ghép đầy đủ trên ~G~ là một tập ~n~ cạnh thuộc ~E~ đôi một không có đỉnh chung. Trọng số của bộ ghép là tổng trọng số các cạnh nằm trong bộ ghép.

Input

• Dòng 1: Chứa số ~n. (1 \leq n \leq 200)~
• Các dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên ~i, j, c~ cho biết có một cạnh ~( x_i, y_j)~ và trọng số cạnh đó là ~c. (0 \le c \le 200)~

Dữ liệu đảm bảo luôn tồn tại ít nhất một bộ ghép đầy đủ trên ~G~.

Output

• Dòng ~1~: Ghi trọng số bộ ghép tìm được.
• ~n~ dòng tiếp theo, mỗi dòng ghi hai số ~(u, v)~ tượng trưng cho một cạnh ~(x_u, y_v)~ được chọn vào bộ ghép.

Sample Input

4
1 1 0
1 2 0
2 1 0
2 4 2
3 2 1
3 3 0
4 3 0
4 4 9

Sample Output

3
1 1
2 4
3 2
4 3

Note

Chú ý dùng Eof chứ không dùng SeekEof.