*【一般图：带权最大匹配】一般图最大权匹配
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
P6699 【模板】一般图最大权匹配
题目背景
模板题，无背景。
题目描述
给定一张有 个顶点的无向带权图，有 条带权边。
求一种匹配的方案，使得最终匹配边的边权之和最大。
输入格式
第一行两个数， 和 。
接下来 行，每行 个数：，，，表示点 与点 之间有一条边权为 的边。
输出格式
第一行一个数，最大边权和。
接下来一行 个整数，描述一组最优方案。第 个整数表示点 匹配的点的编号。如果 号点没有匹配，请输出 0。
输入输出样例 #1
输入 #1
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
输出 #1
28
6 0 4 3 7 1 5
说明/提示
，，。