CF875F Royal Questions

在一个中世纪王国里，经济危机愈演愈烈。牛奶跌价，经济指标每天都在恶化，国库的金钱在不断消失。为了扭转局势，国王查尔斯·桑尼菲斯决定让他 $n$ 个王子儿子娶能带来最大嫁妆的公主。 为寻找候选人，国王向邻国征询，不久后几支代表团带着 $m$ 位未婚公主来到王国。在接待宾客时，查尔斯得知第 $i$ 位公主的嫁妆为 $w_{i}$ 个金币。 尽管故事发生在中世纪，但进步思想已经深入人心，因此任何人都不能强迫公主嫁给她不喜欢的王子。因此，每位公主有机会选择两位自己愿意嫁给的王子。王子们就没那么幸运，在选择新娘的问题上必须服从父亲的意志。 查尔斯已经知道每位公主的嫁妆和她们的偏好，他希望通过安排婚事，使得所有儿子新娘的总嫁妆尽可能多。同时，并非必须让所有王子或所有公主都结婚。每位王子至多只能娶一位公主，同样每位公主最多只能嫁给一位王子。 请帮助国王组织婚姻，使国库获得的金币最多。

第一行包含两个整数 $n$、$m$（$2 \leq n \leq 200000$，$1 \leq m \leq 200000$）——王子的数量和公主的数量。 接下来的 $m$ 行每行包含三个整数 $a_i$、$b_i$、$w_i$（$1\leq a_i, b_i \leq n$，$a_i \neq b_i$，$1\leq w_i \leq 10000$），表示第 $i$ 位公主愿意嫁给的两位王子，以及她的嫁妆数量。

输出一个整数，表示通过合理安排婚事国王最多能获得多少金币。

由 ChatGPT 5 翻译