농장 단순화하기

농부 존은 지역 대학에서 저녁 알고리즘 수업을 듣다가 방금 최소 신장 트리(minimum spanning tree)를 배웠다. 자신의 농장을 살펴본 존은 배치가 더 효율적일 수 있음을 깨닫고, 농장 구조를 단순화하려고 한다.

현재 농장은 그래프로 표현된다. 정점은 밭을 나타내고, 간선은 밭들 사이의 길을 나타내며, 각 길에는 길이가 있다. 존은 어떤 길이든 그 길이를 가진 길이 농장에 최대 세 개까지만 있다는 것을 알아차렸다. 존은 일부 길을 없애서 농장을 트리로 만들고 싶다. 즉, 임의의 두 밭 사이에 정확히 하나의 경로만 존재하도록 만들고 싶다. 더 나아가 이 트리가 최소 신장 트리, 즉 간선 길이의 합이 가능한 한 작은 트리가 되기를 원한다.

농부 존을 도와, 농장 그래프의 최소 신장 트리의 간선 길이 합과, 만들 수 있는 서로 다른 최소 신장 트리의 개수를 구하라. 개수가 클 수 있으므로 $10^9 + 7$으로 나눈 나머지를 출력한다.

• 첫째 줄: 두 정수 $N$과 $M$ ($1 \le N \le 40000$; $1 \le M \le 100000$). 각각 정점과 간선의 개수이며, 정점은 $1 \dots N$로 번호가 매겨진다.
• 둘째 줄부터 $M+1$번째 줄까지: 세 정수 $a_i$, $b_i$, $n_i$ ($1 \le a_i, b_i \le N$; $1 \le n_i \le 1000000$). 정점 $a_i$와 $b_i$를 잇는 길이 $n_i$인 길을 나타낸다. 같은 길이 값 $n_i$는 세 번을 넘겨 등장하지 않는다.

• 첫째 줄: 두 정수. 최소 신장 트리의 길이 합과, 서로 다른 최소 신장 트리의 개수를 $10^9 + 7$으로 나눈 나머지.

길이가 $1$인 두 길을 모두 고르고, 길이가 $2$인 세 길 중 아무거나 하나를 고르면 길이 합이 $4$인 최소 신장 트리가 만들어진다. 길이가 $2$인 길을 고르는 방법이 세 가지이므로, 서로 다른 최소 신장 트리는 $3$개다.