회의

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

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

로 계산할 수 있다.

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

입력 형식

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

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

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

다음 $M$개의 줄의 $i$번째 줄에는 회의를 하는 사람의 시작 건물, 도착 건물과 속도 정보를 나타내는 세 정수 $S_i$, $E_i$, $V_i$가 주어진다. ($1 \le S_i, E_i \le N$, $1 \le V_i \le 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$번 건물에서 회의를 하는게 각 사람의 시간 총 합이 최소가 됨을 알 수 있다.

채점 방식

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

해설