← 返回题目列表

Codeforces · 875/F

F. 皇家问题

中文机器翻译题面 查看原题

在一个中世纪的王国里,经济危机正在肆虐。奶水滴落,经济指标一天天恶化,国库的钱消失了。为了改变这种情况,阳光脸国王查尔斯决定让他的n个儿子王子带着尽可能多的嫁妆迎娶新娘。

为了寻找候选人,国王向邻国询问,过了一会儿,几个代表团带着 m 位未婚公主抵达。卡尔在接待客人时得知,第i位公主的嫁妆是两枚金币。

虽然故事发生在中世纪,但进步思想在社会上广泛传播,任何人都不能强迫公主嫁给她不喜欢的王子。因此,每位公主都有机会选择两名王子,并准备好成为每一位王子的妻子。王子们就没有那么幸运了,他们在选择新娘的问题上都会服从父亲的意愿。

查尔斯知道嫁妆的价值和每位公主的喜好,他希望以这样的方式举办婚礼,让他所有儿子的新娘的嫁妆总额尽可能多。没有必要同时娶所有的王子或公主。每个王子只能娶一位公主,反之亦然,每位公主只能娶一位王子。

帮助国王以对国库最有利的方式组织儿子们的婚姻。

输入

第一行包含两个整数 n, m (2 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000) – 分别是王子和公主的数量。

以下 m 行每行包含三个整数 ai, bi, wi (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ wi ≤ 10 000) – 王子的数量,第 i 个公主准备结婚的以及她的嫁妆的价值。

输出

打印唯一的整数——国王通过参加正确的婚礼可以获得的最大金币数量。

示例

输入 #1

2 3
1 2 5
1 2 1
2 1 10

输出 #1

15

输入 #2

3 2
1 2 10
3 2 20

输出 #2

30