Minimum spanning trees P12887


Statement
 

pdf   zip

thehtml

Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. On a weighted graph, the weight of a spanning tree is the sum of the weights of its edges. A minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.

Input

Input consists of different weighted, connected, undirected graphs. For each graph, the following integers are given: First, n ≥ 1 represents the number of vertices on the graph. Then, m represents the number of edges on the graph. Finally, a set of m weighted edges u,v,w is given by specifying its two end points u and v and its weight w ≥ 1. Vertices are numbered starting from 1. There are no edges connecting a vertex to itself, but there may be more than two edges connecting the same pair of vertices. Every given graph is connected. All weights are strictly positive integers.

Output

For every graph in the input, write the weight of its minimum spanning tree.

Public test cases
  • Input

    5 6
        1 2 3
        1 3 8
        2 4 5
        3 4 2
        3 5 4
        4 5 6
    3 3
        2 1 20
        3 1 20
        2 3 100
    

    Output

    14
    40
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++ Python Python
    User solutions
    C++ Python