회의

NYPC 2019 · 본선

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

배찌의 회사에서는 큰 회의를 할 건물 DD를 정하려고 한다. 회의에는 사람이 MM명 참석하고, MM명의 사람 중 ii번째 사람은 처음에 건물 SiS_i에 있다가 회의가 끝나면 건물 EiE_i로 돌아간다. 또한, ii번째 사람은 ViV_i초에 11미터를 움직일 수 있다. 회의를 할 때는 각 사람은 건물 SiS_i에서 건물 DD까지 갔다가, 회의가 끝난 이후에 건물 DD에서 건물 EiE_i으로 돌아간다. 즉, ii번째 사람의 이동시간은

Vi×(건물 Si과 건물 D의 최단거리)+(건물 D과 건물 Ei의 최단거리)V_i\times {(\textrm{건물 }S_i\textrm{과 건물 }D\textrm{의 최단거리}) + (\textrm{건물 }D\textrm{과 건물 }E_i\textrm{의 최단거리})}

로 계산할 수 있다.

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

입력 형식

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

다음 N1N-1개의 줄의 ii번째 줄에는 도로 양 끝 도시와, 길이 정보를 나타내는 세 정수 AiA_i, BiB_i, CiC_i이 공백으로 구분되어 주어진다. (1Ai,BiN1 \le A_i, B_i \le N, 1Ci10001 \le C_i \le 1\,000)

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

다음 MM개의 줄의 ii번째 줄에는 회의를 하는 사람의 시작 건물, 도착 건물과 속도 정보를 나타내는 세 정수 SiS_i, EiE_i, ViV_i가 주어진다. (1Si,EiN1 \le S_i, E_i \le N, 1Vi10001 \le V_i \le 1\,000)

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

출력 형식

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

예제

입력

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

출력

2

예제 설명

11, 22, 33, 44번 건물에서 회의를 하는데 드는 각 사람의 시간 총 합은 8989, 5353, 6363, 8181이다. 22번 건물에서 회의를 하는게 각 사람의 시간 총 합이 최소가 됨을 알 수 있다.

채점 방식

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

종류 1: 19

N,M100N, M \le 100

종류 2: 16

N,M2000N, M \le 2\,000

종류 3: 26

Si=EiS_i = E_i

종류 4: 18

Ai=iA_i = i, Bi=i+1B_i = i+1

종류 5: 21

별다른 제약조건 없음.

해설