시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 0 0 0 0.000%

문제

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

예제 입력 1

2
6 7
1 2 1
2 3 1
4 5 1
5 6 1
1 4 1
2 5 1
3 6 1
4 5
1 2 1
1 3 1
1 4 1
2 3 1
3 4 1

예제 출력 1

3 3
2 2