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 t1,t2,…,tk, Chiaki would insert edges (u,t1), (t1,t2), (tk−1,tk), (tk,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 (109+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.
Input
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≤n,m≤105) -- the number of vertices and the number of edges. Each of the next m lines contains three integers ui, vi and wi (1≤ui,vi≤n,1≤wi≤109) -- deonting an edge between ui and vi with weight wi. It is guaranteed that neither the sum of all n nor the sum of all m exceeds 106.
Output
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 (109+7).