B. 猫
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
我仿佛看到了一片麦田。

麦田无边无际,阳光照在麦田上、麦穗连在一起,仿佛金色的湖。

她的家人牵着她的手,跑在这风浪中。她笑着跌倒在金色的海洋里,开心地笑着。

——《猫》

良有 $$$n$$$ 条不连贯的与满穗有关的信息,无法将其联系起来。

问过满穗过后,满穗给出了 $$$m$$$ 对信息之间的关系,每一对关系在良眼里都有一个可信度。

良希望用尽可能少的关系把这些信息联系起来,并且整件事情的可信度尽可能的大。

形式化的:给定 $$$n$$$ 个点,$$$m$$$ 条边,每条边有边权。

选择最少数量的边使整个图联通,并且使得边权和最大。

如果无法使得图联通,输出 -1。

Input

第一行输入两个正整数 $$$n$$$,$$$m$$$($$$1\le n \le 10^5$$$,$$$1\le m \le 10^6$$$),分别表示信息和信息关系的数量。

接下来 $$$m$$$ 行,每行输入三个正整数 $$$u_i$$$,$$$v_i$$$,$$$w_i$$$($$$1\le u_i,v_i\le n$$$,$$$1\le w_i \le 10^9$$$),分别表示 $$$u_i$$$ 和 $$$v_i$$$ 信息之间可以连贯,可信度 $$$w_i$$$。

Output

输出一个整数,表示答案。

Example
Input
4 5
1 2 2
3 1 3
2 1 4
3 4 1
2 4 6
Output
13