Những con bò của nông dân John muốn đi lại tự do giữa \(N\) cánh đồng, được đánh số từ \(1\) đến \(N\), trong trang trại. Các cánh đồng bị ngăn cách bởi rừng. Đàn bò muốn bảo dưỡng một số đường mòn nối các cặp cánh đồng để từ bất kỳ cánh đồng nào cũng có thể đi đến mọi cánh đồng khác. Mỗi đường mòn được đi theo cả hai chiều.

Đàn bò không xây đường mới mà chỉ bảo dưỡng những đường mòn của thú rừng đã tìm thấy. Vốn tò mò, đầu mỗi tuần chúng lại phát hiện thêm đúng một đường mòn. Trong tuần đó, chúng chỉ có thể đi trên các đường đang được bảo dưỡng. Chúng được chọn lại bất kỳ tập con nào của tất cả các đường đã biết, không phụ thuộc vào những đường được bảo dưỡng ở tuần trước.

Mục tiêu mỗi tuần là làm cho các cánh đồng liên thông với tổng độ dài đường phải bảo dưỡng nhỏ nhất. Các đường mòn của thú rừng không bao giờ thẳng, kể cả khi được bảo dưỡng; nhiều đường có thể nối cùng một cặp cánh đồng và có độ dài khác nhau. Dù các đường có thể giao nhau, đàn bò vẫn nhất quyết chỉ đổi từ đường này sang đường khác tại một cánh đồng.

Đây là bài tương tác. Sau khi nhận thông tin về đường mới của một tuần, chương trình phải trả lời ngay cho tuần đó trước khi đọc đường mới của tuần tiếp theo.

Dữ liệu vào

• Đọc từ đầu vào chuẩn hai số nguyên \(N,W\), với \(1\le N\le200\) và \(1\le W\le6000\). \(W\) là số tuần.
• Mỗi tuần, đọc một dòng chứa ba số nguyên cách nhau bởi dấu cách: hai đầu mút của đường mòn mới và độ dài của nó. Hai đầu mút là hai cánh đồng khác nhau; độ dài nằm trong khoảng từ \(1\) đến \(10000\).

Dữ liệu ra

Ngay sau khi nhận đường mòn mới, ghi ra đầu ra chuẩn một dòng chứa tổng độ dài nhỏ nhất cần bảo dưỡng để đi được giữa mọi cặp cánh đồng. Nếu chưa thể làm được điều đó, ghi -1.

Đẩy hết dữ liệu trong bộ đệm đầu ra sau mỗi câu trả lời. Kết thúc chương trình sau câu trả lời cho tuần cuối cùng.

Ràng buộc

Giới hạn thời gian: 1 giây CPU. Giới hạn bộ nhớ: 64 MiB.

Phân nhóm

Có 20 bộ dữ liệu, mỗi bộ tối đa 5 điểm. Một bộ dữ liệu chỉ được điểm khi chương trình trả lời đúng tất cả các tuần; không có điểm thành phần trong một bộ dữ liệu.

Ví dụ

4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2

-1
-1
-1
14
12
8

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 1.