Processing math: 100%
Minimum spanning tree - MarisaOJ: Marisa Online Judge

Minimum spanning tree

Time limit: 1000 ms
Memory limit: 256 MB
Given a connected, weighted, undirected graph of n vertices and m edges. Find weight of its minimum spanning tree. _A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight._ ### Input - The first line contain 2 integers n,m. - The next m lines, each line contains 3 integers u,v,w, there is an edge weigh w between u and v. ### Output - Print the weight of the minimum spanning tree. ### Constraints - 1≤n,m≤105. - 1≤u,v≤n. - 1≤w≤109. ### Example Input: 33121232313 Output: 3