영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
A computer network has n computers and n-1 connections between two computers. Information can be exchanged between every pair of computers using the connections.
Each connection has a certain transfer speed. Let d(a,b) denote the transfer speed between computers a and b, which is the speed of the slowest connection on the route between a and b. Your task is to compute the sum of transfer speeds between all pairs of computers.
Input
The first line contains the integer n: the number of computers. The computers are numbered 1,2,…,n.
After this, there are n-1 lines, which describe the connections. Each line has three integers a, b and x: there is a connection between computers a and b with transfer speed x.
Output
Print one integer: the sum of transfer speeds.
Constraints
- 1 ≤ n ≤ 2 · 10^5
- 1 ≤ x ≤ 10^6
Example
Explanation: The following figure corresponds to the sample input:
(그림은 원문 페이지에서 볼 수 있습니다)
Here d(1,2)=5, d(1,3)=1, d(1,4)=2, d(2,3)=1, d(2,4)=2, and d(3,4)=1, so the sum of transfer speeds is 12.
예제
예제 1
4 1 2 5 2 3 1 2 4 2
12