Hãy tưởng tượng, bạn là một công nhân đang thi hành tại thành phố Đà Lạt chiều tím 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 tải năng lượng 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ó thể đi đến các công trình còn lại, và chi phí xây dựng một con đường lớn nhất, 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òng đầu tiên gồm hai số nguyên N, M (1 \leq N \leq 10^5, 1 \leq M \leq 2 \times 10^5).
• M dòng tiếp theo, dòng thứ i chứa ba số nguyên u, v, w (1 \leq u, v \leq N , 1 \leq w \leq 10^9) – mô tả phương án thứ i.

• 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í nhỏ nhất.
• 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.

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