Hãy tưởng tượng, bạn là một công nhân đang làm việc tại thành phố Đà Lạt mộng mơ. Ở đây, bạn phải đi lại giữa ~N~ công trình khác nhau để thực hiện việc thi công. Do thấy việc di chuyển quá nặng nhọc, bạn đã than phiền với sếp của bạn.

Để giảm bớt công sức di chuyển của những công nhân, sếp của bạn đã đề ra ~M~ phương án xây dựng những con đường một chiều giữa các công trình. Về mặt toán học, phương án thứ ~i~ có thể biểu diễn dưới dạng ~u, v, w~, khi đó bạn có thể:

• Xây con đường một chiều nối từ ~u~ đến ~v~ với chi phí là ~w~.

• Xây con đường một chiều nối từ ~v~ đến ~u~ với chi phí là ~w~.

• Không sử dụng phương án này.

Dữ liệu đảm bảo rằng giữa hai công trình chỉ có tối đa một phương án để xây đường, và không có phương án nào xây đường đi từ một công trình đến chính nó.

Đương nhiên, ai than phiền thì người đấy chịu, nên sếp yêu cầu bạn phải chọn lọc trong ~M~ phương án này. Hãy in ra một cách sử dụng các phương án, sao cho từ bất kì công trình nào cũng có thể đi đến các công trình còn lại, và chi phí xây dựng lớn nhất trong các con đường được xây là nhỏ nhất có thể.

Lưu ý: Có thể có nhiều đáp án khác nhau, bạn chỉ cần tìm ra một đáp án bất kì. Nếu không có cách sử dụng các phương án thỏa mãn, in ra một dòng duy nhất chứa số -1.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên ~N, M~ ~(1 \le N \le 10^5,\ 1 \le M \le 2 \cdot 10^5)~.

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u, v, w~ ~(1 \le u, v \le N,\ 1 \le w \le 10^9)~ – mô tả phương án thứ ~i~.

Kết quả

• Nếu không có cách sử dụng các phương án thỏa mãn, in ra một dòng duy nhất chứa số -1.

• Nếu có cách sử dụng, dòng đầu tiên in ra chi phí lớn nhất của một con đường trong cách xây dựng tối ưu.

• ~M~ dòng tiếp theo, dòng thứ ~i~ in ra 0 nếu không sử dụng phương án thứ ~i~, còn nếu sử dụng thì in ra ~u v~ hoặc ~v u~ theo hướng xây dựng con đường một chiều.

Ví dụ

Sample Input 1

3 3
1 2 1
2 3 2
3 1 3

Sample Output 1

3
1 2
2 3
3 1

Sample Input 2

4 5
1 2 1
1 3 2
2 3 4
2 4 3
3 4 3

Sample Output 2

3
1 2
3 1
0
2 4
4 3

Sample Input 3

4 4
1 2 1
2 3 2
3 4 3
4 2 4

Sample Output 3

-1

Giải thích

Đây là hình vẽ mô tả đáp án ví dụ 1 và 2: