Background

$\rm Love ~of ~my ~life$

$\rm U~are~far~from~me$

$\rm U've ~ turned ~ me ~ on$

$\rm and ~ now ~ I ~ try ~ to ~ catch ~ up ~ with ~ you$

$\rm Love ~ of ~ my ~ life ~ can't ~ you ~ see$

$\rm I'll ~ always ~ try, ~ always ~ try$

$\rm U ~ are ~ the ~ brightest ~ star ~ to ~ me$

$\rm No ~ matter ~ others ~ don't ~ know$

$\rm what ~ it ~ means ~ to ~ me$

—— An adaptation of Love of My Life by Queen

This is a template problem with some personal “extras” mixed in.

Problem Description

Given a bipartite graph, both the left part and the right part have $n$ vertices. There are $m$ weighted edges, and it is guaranteed that a perfect matching exists.

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

Input Format

The first line contains two integers $n, m$, with the meaning described above.

Lines $2 \sim m + 1$ each contain three integers $y, c, h$, describing an edge from vertex $y$ on the left part to vertex $c$ on the right part, with edge weight $h$.

Output Format

This problem has a Special Judge.

The first line contains an integer $ans$, the answer.

The second line contains $n$ integers $a_1, a_2, a_3 \cdots a_n$, where $a_i$ is the index of the left-part vertex that is matched with the $i$-th vertex on the right part in the perfect matching. If there are multiple solutions, output any one of them.

5 7
5 1 19980600
4 2 19980587
1 3 19980635
3 4 19980559
2 5 19980626
1 2 -15484297
4 5 -17558732

99903007
5 4 1 3 2 

Hint

Constraints

• For $10\%$ of the testdata, $n \leq 10$.
• For $30\%$ of the testdata, $n \leq 100$.
• For $60\%$ of the testdata, $n \leq 500$, and the testdata is guaranteed to be random.
• For $100\%$ of the testdata, $1 \leq n \leq 500$, $1 \leq m \leq n^2$, $-19980731 \leq h \leq 19980731$. It is also guaranteed that there are no multiple edges.

The testdata was produced after a long time by a problem setter who is “good at causing failures”.

The kind “Yangcunhua” reminds you: do not forget to carefully check the range of edge weights.

The kind “Yangcunhua” reminds you again: your time complexity may only “look” correct.

Translated by ChatGPT 5