최대 가중 매칭

치아키는 특별한 그래프를 만드는 데 능숙하다. 처음에는 간선 하나로 연결된 정점 두 개만 있는 그래프가 있다. 매번 치아키는 간선 $(u,v)$를 하나 고르고 그 간선을 복사한 다음, 복사본 사이에 새 정점을 몇 개(0개일 수도 있다) 삽입할 수 있다. 새 정점을 $t_1,t_2,\dots,t_k$라고 하면, 그래프에 간선 $(u,t_1)$, $(t_1,t_2)$, $\dots$, $(t_{k-1},t_k)$, $(t_k,v)$를 추가한다.

이 연산으로 생성된 가중치 그래프에 대해, 치아키는 그래프의 최대 가중 매칭의 가중치 합과 서로 다른 최대 가중 매칭의 개수를 $10^9+7$로 나눈 나머지로 알고 싶어 한다.

매칭은 서로 인접하지 않은 간선들의 집합이며, 루프는 포함될 수 없다. 즉, 어떤 두 간선도 정점을 공유하지 않아야 한다. 최대 가중 매칭은 간선 가중치의 합이 최대인 매칭이다.

테스트 케이스가 여러 개 주어진다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($1 \le n, m \le 10^5$).

이어서 $m$개의 줄에 정수 $u_i$, $v_i$, $w_i$가 주어진다 ($1 \le u_i, v_i \le n$, $1 \le w_i \le 10^9$). 이는 $u_i$와 $v_i$를 잇는 가중치 $w_i$의 간선이 있음을 뜻한다.

모든 테스트 케이스에 대한 $n$의 합과 $m$의 합은 각각 $10^6$을 넘지 않는다.

각 테스트 케이스마다 두 정수를 공백으로 구분해 출력한다. 첫 번째 정수는 최대 가중 매칭의 가중치 합이다. 두 번째 정수는 서로 다른 최대 가중 매칭의 개수를 $10^9+7$로 나눈 나머지이다.