麦田无边无际,阳光照在麦田上、麦穗连在一起,仿佛金色的湖。
她的家人牵着她的手,跑在这风浪中。她笑着跌倒在金色的海洋里,开心地笑着。
良有 $$$n$$$ 条不连贯的与满穗有关的信息,无法将其联系起来。
问过满穗过后,满穗给出了 $$$m$$$ 对信息之间的关系,每一对关系在良眼里都有一个可信度。
良希望用尽可能少的关系把这些信息联系起来,并且整件事情的可信度尽可能的大。
形式化的:给定 $$$n$$$ 个点,$$$m$$$ 条边,每条边有边权。
选择最少数量的边使整个图联通,并且使得边权和最大。
如果无法使得图联通,输出 -1。
第一行输入两个正整数 $$$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$$$。
输出一个整数,表示答案。
4 51 2 23 1 32 1 43 4 12 4 6
13