철도 2

IOI 나라는 $N$개의 도시와 도시들을 잇는 $N - 1$개의 양방향 철도로 이루어져 있으며, 임의의 서로 다른 두 도시를 철도만을 사용하여 오갈 수 있다. 즉, IOI 나라의 철도망은 트리 구조를 이룬다. 도시에는 각각 $0$ 이상 $N - 1$ 이하의 서로 다른 번호가 붙어 있고, 철도에도 각각 $0$ 이상 $N - 2$ 이하의 서로 다른 번호가 붙어 있다. 모든 $0 ≤ i ≤ N - 2$에 대하여 $i$번 철도는 $U[i]$번 도시와 $V[i]$번 도시를 양방향으로 연결하며, 철도의 길이는 $W[i]$이다.

IOI 나라의 어떤 도시에서 출발하더라도 다른 도시로 직통 열차를 타고 바로 이동할 수 있다. 즉, $0 ≤ u, v ≤ N - 1$, $u \ne v$인 모든 $N(N - 1)$개의 순서쌍 $(u, v)$에 대해, $u$번 도시에서 출발하여 $v$번 도시에 도착하는 직통 열차가 있다. $u$번 도시에서 이 직통 열차를 타면 $v$번 도시에 도착할 때까지 내릴 수 없으며, 이 직통 열차의 소요 시간은 IOI 나라의 철도망에서 $u$번 도시에서 시작하여 $v$번 도시에서 끝나는 유일한 단순 경로 상의 철도들의 길이를 합한 것과 같다.

철도 동호인인 당신은 오랫동안 한 기차를 타면서 여유로움을 느끼는 것을 즐기기 때문에, 소요 시간이 긴 직통 열차만을 타고 다닐수록 더 큰 즐거움을 느낀다.

구체적으로, 서로 다른 두 도시 $x$, $y$에 대해서, 즐거움 $\text{joy}(x, y)$ 는 다음 조건을 만족하는 최대의 양의 정수 $D$로 정의된다:

$x$번 도시에서 시작하여 소요 시간이 $D$ 이상인 직통 열차만을 타고 이동하는 것을 유한 번 반복하여, $y$번 도시에 도착할 수 있다.

$0 ≤ x, y ≤ N - 1$, $x \ne y$를 만족하는 모든 $N(N - 1)$가지의 순서쌍 $(x, y)$에 대한 $\text{joy}(x, y)$의 합을 $1\, 000\, 000\, 007 (= 10^9 + 7)$로 나눈 나머지를 구하는 프로그램을 작성하라.

문제

제한