【模板】二分图最大权完美匹配

题目背景

> $\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 这是一道夹带私货的模板题。

题目描述

给定一张二分图,左右部均有 $n$ 个点,共有 $m$ 条带权边,且保证有完美匹配。 求一种完美匹配的方案,使得最终匹配边的边权之和最大。

输入输出格式

输入格式


第一行两个整数 $n,m$,含义见题目描述。 第 $2\sim m+1$ 行,每行三个整数 $y,c,h$ 描述了图中的一条从左部的 $y$ 号结点到右部的 $c$ 号节点,边权为 $h$ 的边。

输出格式


**本题存在 Special Judge**。 第一行一个整数 $ans$ 表示答案。 第二行共 $n$ 个整数 $a_1,a_2,a_3\cdots a_n$,其中 $a_i$ 表示完美匹配下与**右部**第 $i$ 个点相匹配的左部点的编号。如果存在多种方案,请输出任意一种。

输入输出样例

输入样例 #1

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

输出样例 #1

99903007
5 4 1 3 2 

说明

#### 数据规模与约定 - 对于 $10\%$ 的数据,满足 $n\leq 10$。 - 对于 $30\%$ 的数据,满足 $n\leq 100$。 - 对于 $60\%$ 的数据,满足 $n\leq 500$,且保证数据随机 。 - 对于 $100\%$ 的数据,满足 $1\leq n\leq 500$,$1\leq m\leq n^2$,$-19980731\leq h \leq 19980731$ 。且保证没有重边。 数据由善于出锅的出题人耗时好久制造完成。 善良的杨村花提醒你,别忘了仔细观察一下边权范围哦~ 善良的杨村花又提醒你,你的复杂度可能只是「看起来」很对哦~