P6577 [Template] Maximum Weight Perfect Matching in a Bipartite Graph.

> $\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.

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.

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$.

**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.

#### 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