23315번 - GIANT MIN COST BIPARTITE MATCHING

문제

왼쪽 정점, 오른쪽 정점의 개수가 $N$개, 간선의 개수가 $M$개, 각 정점의 degree가 최대 2인 이분 그래프가 주어진다. 왼쪽 정점과 오른쪽 정점에는 각각 1ドル$부터 $N$까지 번호가 매겨져 있고, 서로 다른 두 정점 사이에는 최대 한 개의 간선이 존재한다.

Matching은 간선의 양 끝점이 중복되지 않게 선택한 간선의 집합을 의미한다. 크기가 1ドル,ドル 2ドル,ドル ..., $N$인 Matching의 최소 비용을 각각 구해보자.

입력

첫 번째 줄에 정점의 개수 $N,ドル 간선의 개수 $M$이 주어진다. (1ドル \le N \le 500,000円,ドル 0ドル \le M \le 2N$)

다음 $M$개의 줄에 걸쳐서 간선의 정보를 나타내는 $(x,y,c)$가 순차적으로 주어진다. $x$는 왼쪽 정점의 번호, $y$는 오른쪽 정점의 번호, $c$는 해당 간선의 비용을 의미한다. (1ドル \le x,y \le N,ドル 1ドル \le c \le 1,000円,000円,000円$)

출력

$N$개의 줄에 걸쳐서 $i$번째 줄에 크기가 $i$인 Matching의 최소 비용을 출력하자. 만약에 이러한 Matching이 없는 경우 -1을 출력한다.

제한

힌트