在一个中世纪的王国里,经济危机正在肆虐。奶水滴落,经济指标一天天恶化,国库的钱消失了。为了改变这种情况,阳光脸国王查尔斯决定让他的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