택시

정점 $N$개로 이루어진 무향 트리가 주어진다. 각 간선에는 길이가 있으며, 이는 양의 정수이다. 이 트리에는 $M$대의 택시와 $M$명의 손님이 나타나며, 각 택시와 각 손님은 정확히 한 정점에 나타난다. 한 정점에 여러 대의 택시나 여러 명의 손님이 있을 수도 있다.

택시 앱은 손님과 택시를 연결해 준다. 요즘은 손님이 택시가 자신을 태우러 가는 거리까지 요금을 낸다. 택시 앱은 몹시 탐욕스러워서, 택시가 각자의 손님에게 이동하는 거리의 합이 최대가 되도록 손님과 택시를 연결한다. 각 택시는 정확히 한 명의 손님에게 배정되고, 각 손님은 정확히 한 대의 택시에 배정된다.

택시와 손님이 트리에 나타나는 서로 다른 경우의 수는 $N^{2M}$가지이다. 각 경우마다 택시 앱이 고른 탐욕스러운 연결에 따라 택시가 이동하는 거리의 합을 구할 수 있다. 이 거리들을 모두 더한 값을 $10^9 + 7$로 나눈 나머지를 구하시오.

첫 번째 줄에 두 정수 $N$과 $M$이 주어진다 ($1 \le N, M \le 2500$).

다음 $N - 1$개의 줄에 각각 세 정수 $x$, $y$, $l$이 주어진다. 이는 정점 $x$와 $y$ 사이에 길이 $l$인 무향 간선이 있음을 뜻한다 ($1 \le l \le 10\,000$). 주어진 간선들이 트리를 이룸이 보장된다.

필요한 합을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.