Giant Min Cost Bipartite Matching

The bipartite graph has $N$ vertices on the left side, $N$ vertices on the right side, and $M$ edges. Every vertex has degree at most 2. Left and right vertices are each numbered from $1$ to $N$, and two vertices are joined by at most one edge.

A matching is a set of edges where no two edges share an endpoint. For each size $1$, $2$, $\ldots$, $N$, find the minimum cost of a matching of that size.

The first line contains $N$ and $M$, the number of vertices and the number of edges. ($1 \le N \le 500\,000$, $0 \le M \le 2N$)

Each of the next $M$ lines contains $(x, y, c)$: $x$ is the left vertex, $y$ is the right vertex, and $c$ is the cost of that edge. ($1 \le x, y \le N$, $1 \le c \le 1\,000\,000\,000$)

Print $N$ lines. Line $i$ contains the minimum cost of a matching of size $i$. If no such matching exists, print -1.