Start: Feb, 04, 2024 16:00:00
20240205并查集+最小生成树
End: Apr, 04, 2024 20:00:00
Time elapsed:
Time remaining:

最小生成树MST 1240

Time Limit:  1 Sec    Memory Limit:   128 MB
Submission:39     AC:12     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