18981번 - 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$).