패킷 라우팅

때는 1969년 10월 29일. 이날 UCLA의 과학자들은 네트워크를 통해 두 대의 컴퓨터 사이에서 데이터를 주고받으며 역사를 만들었다. 전송된 내용은 그리 대단하지 않았다. 시스템이 멈추기 전까지 단어 login 중 앞의 두 글자만 전달되었을 뿐이다. 그럼에도 연구자들은 더 큰 컴퓨터 네트워크를 설계하기 시작했고, 당신의 도움이 필요하다.

컴퓨터 네트워크는 $N$ $(2 \le N \le 100)$대의 컴퓨터와 $W$개의 전선으로 이루어져 있다. 컴퓨터는 $1, 2, \dots, N$의 번호로 구분된다. 각 전선은 정확히 두 대의 컴퓨터를 연결하며, 데이터 패킷이 두 컴퓨터 사이를 양방향으로 흐를 수 있게 한다. 전선은 모든 컴퓨터 쌍 사이에서 (직접 또는 다른 컴퓨터를 거쳐 간접적으로) 패킷을 보낼 수 있도록 배치되어 있다. 실제로 전선의 배치는 최적화되어 있어, 모든 컴퓨터 쌍 사이에 경로가 정확히 하나만 존재한다. 패킷이 출발지 컴퓨터에서 목적지 컴퓨터까지 여러 전선을 거쳐 이동하면, 그 경로를 지나는 데 필요한 시간은 각 전선을 지나는 데 필요한 시간의 합이다. 서로 다른 두 컴퓨터가 주어질 때, 패킷이 그 사이를 이동하는 데 걸리는 시간을 구하는 프로그램을 작성하라.

첫째 줄에 세 양의 정수 $N$, $W$, $P$가 주어진다.

이어서 각 전선마다 한 줄씩, 그 전선이 연결하는 두 컴퓨터의 번호와, 그 전선을 지나는 데 필요한 시간을 나타내는 $1$ 이상 $500$ 이하의 정수가 주어진다.

$P$ $(1 \le P \le 10\,000)$는 보내야 하는 패킷의 개수이다. 이어서 각 패킷마다 한 줄씩, 그 패킷의 출발지와 목적지 컴퓨터의 번호가 주어진다.

각 패킷에 대해 출발지 컴퓨터에서 목적지 컴퓨터까지의 경로를 찾아, 그 경로의 이동 시간을 한 줄에 하나씩 출력한다.