거대 최소 비용 이분 매칭

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

매칭(Matching)은 간선의 양 끝점이 중복되지 않도록 고른 간선의 집합이다. 크기가 $1$, $2$, $\ldots$, $N$인 매칭 각각에 대해 최소 비용을 구해 보자.

첫 번째 줄에 정점의 개수 $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$인 매칭의 최소 비용을 출력한다. 그러한 매칭이 없으면 -1을 출력한다.