← 목록으로

회의

배찌의 회사는 N개의 건물과 N-1개의 도로로 이루어져 있다. 편의를 위해서, 건물에 1번부터 N번까지, 도로에 1번부터 N-1번까지 번호를 매기자. 도로 i는 건물 Ai와 건물 Bi를 양방향으로 연결하고, 길이는 Ci 미터 이다. 배찌의 회사에 있는 임의의 두 건물에 대해서, 한 개 이상의 도로를 사용하여 두 건물을 서로 오갈 수 있다.

배찌의 회사에서는 큰 회의를 할 건물 D를 정하려고 한다. 회의에는 사람이 M명 참석하고, M명의 사람 중 i번째 사람은 처음에 건물 Si에 있다가 회의가 끝나면 건물 Ei로 돌아간다. 또한, i번째 사람은 Vi초에 1미터를 움직일 수 있다. 회의를 할 때는 각 사람은 건물 Si에서 건물 D까지 갔다가, 회의가 끝난 이후에 건물 D에서 건물 Ei으로 돌아간다. 즉, i번째 사람의 이동시간은 Vi×{(건물 Si과 건물 D의 최단거리) + (건물 D과 건물 Ei의 최단거리)}로 계산할 수 있다.

배찌의 회사는 효율을 중요시 여기기 때문에 각 사람이 이동하는 데 드는 시간의 합을 최소화하도록 건물 D를 정하고 싶다. 각 사람이 이동하는 데 드는 시간의 합이 최소가 되는 건물 D를 구하여라.

입력 형식

첫째 줄에는 건물의 개수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N-1개의 줄의 i번째 줄에는 도로 양 끝 도시와, 길이 정보를 나타내는 세 정수 Ai, Bi, Ci이 공백으로 구분되어 주어진다. (1 ≤ Ai, Bi ≤ N, 1 ≤ Ci ≤ 1,000)

그 다음 줄에는 회의에 참석하는 사람의 수 M이 주어진다. (1 ≤ M ≤ 100,000)

다음 M개의 줄의 i번째 줄에는 회의를 하는 사람의 시작 건물, 도착 건물과 속도 정보를 나타내는 세 정수 Si, Ei, Vi가 주어진다. (1 ≤ Si, Ei ≤ N, 1 ≤ Vi ≤ 1,000)

배찌의 회사에 있는 임의의 두 건물에 대해서, 한 개 이상의 도로를 사용하여 두 건물을 서로 오갈 수 있다.

출력 형식

첫째 줄에 정수 D를 출력하여라. 이는, 각 사람이 이동하는데 드는 시간의 합이 최소가 되는 회의 장소가 건물 D라는 의미이다. 답이 여러개인 경우 아무거나 출력하여도 좋다.

입력 예제

4
2 1 3
2 3 5
2 4 7
3
4 2 1
2 3 2
3 4 3

출력 예제

2

예제 설명

1, 2, 3, 4번 건물에서 회의를 하는데 드는 각 사람의 시간 총 합은 89, 53, 63, 81이다. 2번 건물에서 회의를 하는게 각 사람의 시간 총 합이 최소가 됨을 알 수 있다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설