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 \le n \le 10000$.

Output

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