Minimizing the cost of a graph P36054

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.