Cheapest cycle P18546


Statement
 

pdf   zip

html

You are given an undirected graph with positive costs at the edges. Please compute the cheapest cycle of the graph.

Input

Input consists of several cases, each with the number of vertices n, followed by the number of edges m, followed by m triples x y c to indicate an edge connecting x and y with cost c, where xy and 1 ≤ c ≤ 106. Vertices are numbered starting from 0. For every pair of vertices, there is at most one edge connecting them. Assume 3 ≤ n ≤ 1000 and nm ≤ 5n.

Output

For every case, print the cost of the cheapest cycle of the graph.

Public test cases
  • Input

    3 3
    0 1 10  0 2 20  1 2  30
    7 8
    5 0 70  4 5 10  0 4 40  2 1 40  3 6 1  5 2 30  4 1 30  4 2 80
    

    Output

    60
    110
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Catorzè Concurs de Programació de la UPC - Semifinal
    Date
    2016-06-29