시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 1 1 50.000%

문제

Farmer John's cows wish to travel freely among the N (1 ≤ N ≤ 200) fields (numbered 1…N) on the farm, even though the fields are separated by forest. The cows wish to maintain trails between pairs of fields so that they can travel from any field to any other field using the maintained trails. Cows may travel along a maintained trail in either direction.

The cows do not build trails. Instead, they maintain wild animal trails that they have discovered. On any week, they can choose to maintain any or all of the wild animal trails they know about.

Always curious, the cows discover one new wild animal trail at the beginning of each week. They must then decide the set of trails to maintain for that week so that they can travel from any field to any other field. Cows can only use trails which they are currently maintaining.

The cows always want to minimize the total length of trail they must maintain. The cows can choose to maintain any subset of the wild animal trails they know about, regardless of which trails were maintained the previous week.

Wild animal trails (even when maintained) are never straight. Two trails that connect the same two fields might have different lengths. While two trails might cross, cows are so focused, they refuse to switch trails except when they are in a field.

At the beginning of each week, the cows will describe the wild animal trail they discovered. Your program must then output the minimum total length of trail the cows must maintain that week so that they can travel from any field to any other field, if there exists such a set of trails.

입력

  • The first line of input contains two space-separated integers, N and W. W is the number of weeks the program will cover (1 ≤ W ≤ 6000).
  • For each week, read a single line containing the wild animal trail that was discovered. This line contains three space-separated integers: the endpoints (field numbers) and the integer length of that trail (1…10000). No wild animal trail has the same field as both of its endpoints.

출력

Immediately after your program learns about the newly discovered wild animal trail, it should output a single line with the minimum total length of trail the cows must maintain so that they can travel from any field to any other field. If no set of trails allows the cows to travel from any field to any other field, output “-1”.

Your program must exit after outputting the answer for the last week.

예제 입력 1

4 6
1 2 10

1 3 8

3 2 3

1 4 3

1 3 6

2 1 2

예제 출력 1


-1

-1

-1

14

12

8

채점 및 기타 정보

  • 예제는 채점하지 않는다.