28244번 - 사람이 먼저 되라

문제

송도고의 교시_校是는 "사람이 먼저 되라"이다.

재작년에 송도고에 입학한 도훈이는 등교할 때 바위에 쓰인 이 글귀를 읽었다. 하지만 도훈이는 이 글귀를 정말로 사람이 되어야 한다는 것으로 이해하여, 100일간 먹을 질 좋은 마늘과 쑥을 찾아다니기 시작했다.

2021년 겨울에 송도고등학교 정문에서 찍은 교시가 적힌 바위이다.

우선 도훈이는 2년 반 동안 전 세계의 마늘을 비교하여 최고의 마늘을 찾아내었다. 이제 쑥만 고르면 된다. 하지만 도훈이는 졸업 전까지 100일간 마늘과 쑥을 먹고 사람이 될 계획이었는데, 마늘을 고르고 나니 시간이 얼마 남지 않게 되었다!

쑥은 $n$개의 정점과 $n-1$개의 가중치를 가진 간선으로 이루어진 트리로 표현할 수 있다. 트리로 표현한 쑥의 가치는 다음과 같이 정의된다.

• 각 단순 경로에 대해 맛은 경로 위 간선들의 가중치 합이 된다.
• 각 단순 경로에 대해 향은 경로 위 간선들의 가중치 최댓값이 된다.
• 간선을 하나 이상 포함하는 모든 단순 경로에 대한 맛과 향의 곱을 더한 값이 쑥의 가치이다.
• 이때, 단순 경로의 방향은 구분하지 않는다.

도훈이가 쑥을 빠르게 고를 수 있도록, 주어진 쑥의 가치를 구하는 프로그램을 작성하여라. 단, 쑥의 가치가 매우 커질 수 있으므로 쑥의 가치를 10ドル^9+7$로 나눈 나머지를 출력한다.

입력

첫 번째 줄에 정점의 개수 $n$이 주어진다.

이어서 $n-1$개의 줄에 각각 간선의 정보를 나타내는 정수 $u,ドル $v,ドル $w$가 차례대로 주어진다. 이는 간선이 $u$와 $v$를 연결하며, $w$의 가중치를 지닌다는 의미이다.

출력

주어진 쑥의 가치를 10ドル^9+7$로 나눈 나머지를 출력하여라.

제한

• 2ドル ≤ n ≤ 200,000円$.
• 1ドル\le u, v\le n$.
• 각 $(u,v,w)$쌍에 대해 $u\neq v$이다.
• 1ドル\le w\le 10^9$.
• 주어지는 그래프는 트리임이 보장된다.

노트

• 트리는 사이클이 없는 연결 그래프이다.
• 트리에서 단순 경로는 두 정점을 연결하는 경로 중 사용하는 간선의 수가 최소인 경로이다.