Start: Oct, 03, 2021 07:00:00
专题4 最短路算法 + 专题5 二分答案,并查集,最小生成树
End: Oct, 23, 2021 11:00:00
Time elapsed:
Time remaining:

最小生成树MST 1240

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:53     AC:13     Score:100


Description

生成树:一个有n个结点的连通图的生成树是原图的极小连通子图,包含原图中的所有n个结点,并且有保持图连通的最少的边。

最小生成树:生成树中权值最小的一种方案。

给定一个无向图,请输出最小生成熟的权值。

存在重边

Input

第一行包含三个整数N、M,分别表示点的个数、边的个数;

接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条边的两个点和长度。

Output

输出最小生成熟的权值,如果答案不存在,请输出-1。

Samples

input:
4 6 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
output:
5

Hint

对于100%的数据:N<=1000,M<=400000