키보토스의 블랙마켓은 개의 구역과, 구역 사이를 잇는 개의 도로로 이루어져 있다. 번 도로는 구역 와 를 의 길이로 잇는 도로이다. 또한, 임의의 두 구역 사이에는 항상 유일한 경로가 존재한다. 즉, 블랙마켓은 트리 구조를 이룬다.
번 구역에는 상점 가 위치해 있다. 내일, 상점은 처음으로 개점을 할 것이다. 첫 개점이기 때문에, 모든 개의 구역으로부터 이 상점을 방문하기 위해 이동할 것이다.
하지만 사람이 한 곳에 너무 많이 몰리면 불만이 생길 수 있으므로, 한 구역에 가맹점을 하나 설치해, 각 구역에서는 본점과 가맹점 중 더 가까운 곳을 방문하게 하려고 한다. 모든 구역의 접근성을 고려하여, 다음 값을 최소화하려고 한다. 이 때, 는 가맹점의 위치이다.
(단, 는 구역 와 구역 사이의 거리)
에 대해, 적절히 가맹점을 잡았을 때 위 식의 최솟값을 구해주자.
첫 번째 줄에 양의 정수 이 주어진다.
두 번째 줄부터 개의 줄에 걸쳐 세 양의 정수 가 공백을 사이에 두고 주어진다.
개의 정수를 공백을 사이에 두고 출력한다. 번째 정수는 일 때의 위 식의 최솟값을 뜻한다.
