문제

때는 서기 3023년, 과학기술의 발전에 힘입어 한양대학교는 건물 사이를 이동할 수 있는 순간이동 포탈을 설치하기로 했다.

한양대학교는 번부터 번까지 총 개의 건물이 있고, 개의 도로가 건물들 사이를 연결하고 있다. 모든 건물 쌍에는 그 건물을 연결하는 유일한 경로가 존재한다. 즉, 트리 구조를 이룬다.

조사 끝에 a번 건물과 b번 건물 사이를 이동하는 포탈을 설치하면 (번 건물을 이용하는 학생 수) + (번 건물을 이용하는 학생 수) - (번 건물과 번 건물 사이의 거리) 만큼의 수익을 낼 수 있음이 밝혀졌다.

철민이는 포탈을 하나 설치했을 때 낼 수 있는 최대 수익을 알아내기로 계획했다. 먼저 학교를 돌아다니면서 각 건물들을 이용하는 학생의 수와, 각 도로들의 길이를 기록해 두었다. 그러나 막상 개의 쌍을 모두 계산하기에는 너무나도 귀찮아, 여러분에게 맡기고 발로란트를 하러 가버렸다.

포탈을 하나 설치했을 때 낼 수 있는 최대 수익은 얼마일까? 만약 어떠한 포탈도 양의 수익을 낼 수 없다면 0을 출력하면 된다.

입력

첫째 줄에 건물의 수 이 주어진다.

둘째 줄부터 개의 줄에 걸쳐 도로를 나타내는 세 정수 가 공백으로 구분하여 주어진다. 번 건물과 번 건물을 연결하는 길이 의 양방향 도로를 의미한다.

다음 줄에는 개의 정수 이 공백으로 구분하여 주어진다. 는 번 건물을 이용하는 학생 수를 의미한다.

출력

포탈을 하나 설치했을 때 낼 수 있는 최대 수익을 출력한다. 만약 어떠한 포탈도 양의 수익을 낼 수 없다면 0을 출력한다.