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