Maximum Weight Bipartite Matching

Problem Description

Once upon a time there was a harmonious class, with $n_l$ boys and $n_r$ girls, numbered $1, \dots, n_l$ and $1, \dots, n_r$ respectively.

There are several such conditions: the $v$-th boy and the $u$-th girl are willing to become spouses, and if they do, their happiness is $w$.

What is the maximum total happiness in this class?

Input Format

The first line contains three positive integers $n_l, n_r, m$.

The following $m$ lines each contain three integers $v, u, w$, meaning the $v$-th boy and the $u$-th girl are willing to become spouses, with happiness $w$. It is guaranteed that $1 \leq v \leq n_l$, $1 \leq u \leq n_r$, and the same pair $(v, u)$ does not appear twice.

It is guaranteed that $1 \leq n_l, n_r \leq 400$, $1 \leq m \leq 160000$, $1 \leq w \leq 10^9$.

Output Format

The first line outputs one integer: the maximum possible total happiness.

The next line outputs $n_l$ integers describing one optimal scheme. The $v$-th integer is the index of the spouse of boy $v$. If boy $v$ has no spouse, output $0$.

Sample Input

2 2 3
1 1 100
1 2 1
2 1 1

Sample Output

100
1 0

Constraints

$1 \leq n_l, n_r \leq 400$, $1 \leq m \leq 160000$, $1 \leq w \leq 10^9$.

Hint

• This is the assignment problem / maximum-weight bipartite matching, solvable with the Kuhn-Munkres (Hungarian) algorithm or with a minimum-cost maximum-flow formulation. Output any optimal matching.