Description

Given an undirected weighted graph with $n$ vertices and $m$ weighted edges.

Find a matching such that the sum of the weights of the matched edges is maximized.

Input Format

The first line contains two numbers, $n$ and $m$.

The next $m$ lines each contain three numbers: $u$, $v$, $w$, indicating that there is an edge between vertex $u$ and vertex $v$ with weight $w$.

Output Format

The first line contains one number: the maximum total edge weight.

The next line contains $n$ integers, describing one optimal solution. The $v$-th integer is the index of the vertex matched with vertex $v$. If vertex $v$ is not matched, output 0.

7 20
5 7 9
3 7 4
3 6 6
2 5 8
5 1 9
1 3 6
6 5 1
2 7 4
2 3 5
6 4 2
7 1 5
5 4 4
4 1 3
5 3 9
7 6 4
2 1 3
4 3 9
6 2 7
4 2 8
6 1 10

28
6 0 4 3 7 1 5

Hint

Constraints: $1 \le n \le 400$, $1 \le m \le 79800$, $1 \le w \le 5\times10^8$.

Translated by ChatGPT 5