34958번 - Protect the SSHS 서브태스크스페셜 저지

문제

서울과학고는 1ドル$부터 $N$까지의 번호가 매겨진 건물 $N$개가 $M$개의 양방향 도로로 연결되어 있고, 각 도로의 길이는 $w$이다. $N$개의 건물 중 1ドル$번 건물은 정문이고, $N$번 건물은 후문이다. 서울과학고의 각 도로는 서로 다른 두 건물을 연결하고, 같은 도로는 여러 개 존재하지 않는다. 또한, 모든 건물은 도로를 통해 연결되어 있다. 즉, 서울과학고의 도로망은 단순 연결 그래프 형태이다.

항상 서울과학고를 노리던 경기과학고의 악당 민재와 유담이가 각각 정문과 후문에서 요새를 향해 최단 경로로 침입하려고 한다. 민재는 거리 1ドル$을 이동하는 데 $a$초가 걸리고, 유담이는 거리 1ドル$을 이동하는 데 $b$초가 걸린다. 경기과학고 악당들의 계획을 알게 된 서울과학고 학생들은 가장 안전한 건물 하나를 요새로 만들려고 한다. 요새는 민재와 유담이 중 적어도 한 명이 도착하기까지 걸리는 시간이 모든 $N$개의 건물 중 최대여야 한다.

서울과학고는 $Q$개의 $(a,b)$ 순서쌍으로 시나리오를 만들어 민재와 유담이의 침입을 대비하기로 했다. 모든 $Q$개 시나리오에 대해 서울과학고 학생들이 선택해야 하는 요새의 건물 번호를 각각 찾아보자.

입력

첫째 줄에 서울과학고 건물의 수 $N$과 도로의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐 양방향 도로를 통해 연결된 두 건물의 번호 $u,ドル $v$와 도로의 길이 $w$가 공백으로 구분되어 주어진다.

$M+2$번째 줄에 준비한 시나리오의 수 $Q$가 주어진다.

이어서 $Q$개의 줄에 걸쳐 각 시나리오에서 두 악당의 속력과 관련된 정수 $a,ドル $b$가 공백으로 구분되어 주어진다.

출력

첫째 줄부터 $Q$개의 줄에 걸쳐 각 시나리오에서 서울과학고 학생들이 정할 요새의 건물 번호를 한 줄에 하나씩 순서대로 출력한다. 학생들이 정할 수 있는 요새가 여러 개여도 하나만 출력하면 된다.

제한

• 2ドル \le N \le 100,000円$
• $N-1 \le M \le 300,000円$
• 1ドル \le u, v \le N,ドル $u \neq v$
• 1ドル \le w \le 10^6$
• 1ドル \le Q \le 200,000円$
• 1ドル \le a, b \le 10^6$

서브태스크

노트