#2433 대역폭

10  1 s   128 MB  

Description

N 명의 친구들이 있습니다. 이 N 명은 서로 다른 지역에 살고 있어, 서로의 통신을 위해 두 사람 간을 연결하는 회선 N − 1개를 설치하였습니다.
물론 여러 개의 회선을 거치면 어떤 두 사람 간에도 통신이 가능하게 설치되어 있으며, 두 사람 간에 통신을 할 때는 이용하는 회선의 개수가 가장 작게 회선을 거쳐서 통신하게 됩니다.
전체 회선이 트리 형태이므로 두 사람 간의 통신에 사용되는 회선의 집합은 유일하게 결정됩니다.
 
각 회선에는 대역폭이 있어서 통신에 이용하는 회선 중 가장 대역폭이 작은 지점이 병목이 발생하여 전체 통신이 느려지게 되며, 이 대역폭에 맞춰 통신을 진행하게 됩니다.
만약 다수가 통신할 경우는 참여하는 모든 두 사람의 쌍에 대해 이용하게 되는 회선을 고려하여 그 중의 가장 대역폭이 작은 값에 맞춰서 통신을 진행하게 됩니다.
N 명의 부분집합 중 크기가 2이상인 모든 부분집합 (2명 이상의 친구가 통신에 참여하는 경우) 에 대해 그 사람들 간의 통신에서 사용하는 회선 대역폭의 최솟값의 합을 구하는 프로그램을 작성하세요.
 
 
위 그림은 첫 번째 입력 예시를 나타냅니다. 빨간색 정점은 부분집합에 속해 있는 정점, 하얀색 정점은 부분집합에 속해 있지 않은 정점입니다.
빨간색 간선은 통신에 사용되는 간선, 검은색 간선은 통신에 사용되지 않는 간선입니다. 순서대로 사용된 간선의 대역폭의 최솟값은 1, 2, 1, 1이므로 답은 1 + 2 + 1 + 1 = 5입니다.
 

Input

입력의 첫째 줄에는 친구의 수 N (2 ≤ N ≤ 105)이 주어집니다.
다음 N − 1개의 줄에는 x, y, w (1 ≤ x, y ≤ N, 0 ≤ w ≤ 106)이 주어지며, 이는 x와 y를 연결하는 대역폭이 w인 간선이 존재한다는 뜻입니다. 같은 줄의 인접한 숫자 사이는 공백으로 구분됩니다.

Output

N 명에 대한 부분집합 중 크기가 2 이상인 모든 부분집합에 대해 그 사람들 간의 통신에서 사용하는 회선 대역폭의 최솟값의 합을 1,000,000,007로 나눈 나머지를 출력합니다.

Sample Input

Sample Output

3
1 2 1
1 3 2
5

Source

shake! 2015 본선