Maximum Weighted Matching

Chiaki is good at generating special graphs. Initially, she has a graph with only two vertices connected by an edge. Each time, she can choose an edge $(u,v)$, make a copy of it, insert some new vertices (maybe zero) in the edge (i.e. let the new vertices be $t\_1,t\_2,\dots,t\_k$, Chiaki would insert edges $(u,t\_1)$, $(t\_1,t\_2)$, $\dots$, $(t\_{k-1}, t\_k)$, $(t\_k, v)$ into the graph).

Given a weighted graph generated by above operations, Chiaki would like to know the maximum weighted matching of the graph and the number different maximum weighted matchings modulo ($10^9 + 7)$).

A matching in a graph is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share a common vertex.

A maximum weighted matching is defined as a matching where the sum of the values of the edges in the matching have a maximal value.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) -- the number of vertices and the number of edges.

Each of the next $m$ lines contains three integers $u\_i$, $v\_i$ and $w\_i$ ($1 \le u\_i, v\_i \le n, 1 \le w\_i \le 10^9$) -- deonting  an edge between $u\_i$ and $v\_i$ with weight $w\_i$.

It is guaranteed that neither the sum of all $n$ nor the sum of all $m$ exceeds $10^6$.

For each test case, output two integers separated by a single space. The first one is the sum of weight and the second one is the number of different maximum weighted matchings modulo ($10^9 + 7$).