Giải bài trực tuyến

Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, ..., xn, các đỉnh của Y ký hiệu là y1, y2, ..., yn. 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.

Ràng buộc: Luôn tồn tại ít nhất một bộ ghép đầy đủ trên G.
Chú ý dùng Eof chứ không dùng SeekEof

Input

• Dòng 1: Chứa số n (1 ≤ n ≤ 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 (xi, yj) và trọng số cạnh đó là c (0 ≤ c ≤ 200).

Output

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

Example

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


Output:
3
1 1
2 4
3 2
4 3