Farmer John은 지역 대학의 저녁 알고리즘 수업에서 최소 신장 트리를 배웠습니다. 농장 설계가 더 효율적일 수 있다는 것을 깨닫고 배치를 단순화하려 합니다.

농장은 그래프처럼 구성되어 정점은 밭, 간선은 밭 사이의 길이며 각 길에는 길이가 있습니다. Farmer John은 같은 길이의 길이 최대 세 개임을 알아챕니다. FJ는 일부 길을 없애 모든 밭 쌍 사이에 유일한 경로가 있는 트리를 만들려 합니다. 또 간선 길이 합이 최소인 최소 신장 트리를 원합니다.

Farmer John을 도와 농장 그래프의 최소 신장 트리 길이 합과 만들 수 있는 서로 다른 최소 신장 트리의 개수를 구하세요.

입력

• 줄 $1$: 정점 수와 간선 수인 두 정수 $N$, $M$, $1 \le N \le 40,000; 1 \le M \le 100,000$입니다. 정점 번호는 $1\ldots N$입니다.
• 줄 $2\ldots M+1$: 세 정수 $a_{i}$, $b_{i}$, $n_{i}$, $1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$은 $a_{i}$에서 $b_{i}$까지 길이 $n_{i}$인 간선을 나타냅니다. 같은 길이 $n_{i}$는 세 번보다 많이 나타나지 않습니다.

출력

• 줄 $1$: 최소 신장 트리의 길이와 개수 (개수는 $1,000,000,007$로 나눈 나머지)인 두 정수.

예제

입력 1

4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 2

출력 1

4 3

참고

길이 $1$인 두 간선과 길이 $2$인 임의의 간선을 선택하면 길이 $4$인 최소 신장 트리가 됩니다.

문제 출제: Nathan Pinsker, 2011