Minimizing the cost of a graph P36054


Statement
 

pdf   zip

html

Consider a connected, undirected multigraph G with labels at the edges. Define the cost of G as the sum of its labels. You must compute the minimum cost c that can be obtained after removing zero or more edges without disconnecting G. Among all the solutions that achieve cost c, you must also compute the minimum number of remaining edges m, and the maximum number of remaining edges M.



For instance, consider these two graphs:

The minimum possible cost of the first graph is 8, and there is just one way to achieve it, namely removing one of its seven edges: the 1–2 edge. Thus c = 8, m = M = 6. As for the second graph, it is easy to see that c = −6, m = 2, and M = 4.

Input

Input is all integers, and consists of several descriptions of connected multigraphs. Every description starts with the number of vertices n and the number of edges e. Then follow e triples, one for every edge, with its two vertices and its label in this order. The vertices are numbered from 0 to n − 1. Assume 0 ≤ n ≤ 10000.

Output

For every given graph, output c, m and M in one line.

Public test cases
  • Input

    6 7
    0 1 3   0 2 5   1 2 7   2 3 15
    4 5 -7      3 4 -5      3 5 -3
    
    2 4
    1 0 0
    0 0 0
    0 1 -3
    1 0 -3
    

    Output

    8 6 6
    -6 2 4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Quart Concurs de Programació de la UPC - Final
    Date
    2006-10-04