알파카 왕국은 \(N\) 개의 목장으로 이루어져 있다. 목장들은 \(N-1\) 개의 길로 이어져 있어 어떤 두 목장 사이에도 길을 따라가는 경로가 유일하게 하나 존재한다. 즉 목장들은 트리를 이룬다. 각 길에는 알파카가 그 길을 거닐 때 느끼는 만족도 \(W\) 가 적혀 있다.

산책을 좋아하는 알파카는 한 목장에서 다른 목장으로 갈 때, 지나온 길들의 만족도 중 가장 큰 값에서 가장 작은 값을 뺀 차이, 즉 만족도의 편차 만큼 즐거움을 느낀다. 예를 들어 경로에 만족도 \(5, 2, 5\) 인 길이 있었다면 이번 산책의 편차는 \(5 - 2 = 3\) 이다.

알파카는 모든 목장의 쌍 \((a, b)\) 에 대해 한 번씩 산책했을 때 느끼는 편차의 총합이 궁금하다. \((a, b)\) 와 \((b, a)\) 는 같은 산책으로 친다. 이 총합을 구해 알파카를 도와주자.

• \(1 \le N \le 100{,}000\)

• \(1 \le X, Y \le N\), \(X \ne Y\)

• \(1 \le W \le 200\)

• 모든 입력값은 정수이다.

• 주어지는 그래프는 항상 트리이다. 답은 \(64\) 비트 정수 범위에 들어간다.

첫째 줄에 목장의 수 \(N\) 이 주어진다.

이어지는 \(N-1\) 개의 줄에 각각 세 정수 \(X, Y, W\) 가 주어진다. 이는 목장 \(X\) 와 목장 \(Y\) 가 길로 이어져 있으며 그 길의 만족도가 \(W\) 라는 뜻이다.

모든 목장의 쌍에 대해 산책했을 때 알파카가 느끼는 만족도 편차의 총합을 한 줄에 출력한다.

psy1 작성

출처 알파카컵 2회