모험을 떠나자

한신이는 당내 최고의원으로 뽑히지 못하자 그 책임을 지고 의원직에서 물러났다. 그리고 새로운 재미를 찾아 미국 동부로 모험을 떠났다. 버지니아에 사는 친구에게 차를 빌렸지만 넣어 둔 기름이 한정되어 있어서, 갈 수 있는 거리 안에서 버지니아 곳곳을 돌아보기로 했다.

친구에게서 각 지역의 가치를 들은 한신이는 기름이 바닥나지 않는 선에서 출발지부터 도착지까지 지나는 지역의 가치 합을 최대로 만들려고 한다.

여행의 목적은 오직 재미이므로 같은 도시를 여러 번 지나도 된다. 다만 가치는 처음 지날 때 한 번만 더하고 두 번째부터는 더하지 않는다. 가치 합에는 출발지와 도착지도 포함한다.

첫째 줄에 방문할 수 있는 지역의 수 $c$가 주어진다. 이어지는 $c$개 줄에는 지역의 이름과 그 지역의 가치가 공백으로 구분되어 주어진다.

다음 줄에 지역 사이를 잇는 도로의 수 $m$이 주어진다. 이어지는 $m$개 줄에는 도로가 잇는 두 지역의 이름과 그 도로의 길이가 주어진다. 도로의 길이는 정수이고 모든 도로는 양방향으로 다닐 수 있다. 같은 두 지역을 잇는 도로가 여러 개 주어질 수도 있고, 한 지역에서 자기 자신으로 이어지는 도로가 주어질 수도 있다.

다음 줄에 테스트 케이스의 수 $p$가 주어진다. 이어지는 $p$개 줄에는 출발지, 도착지, 이동할 수 있는 최대 거리가 주어진다.

모든 값은 공백으로 구분되고 지역 이름 안에는 공백이 없다. 예를 들어 Virginia Beach처럼 띄어 쓴 이름은 입력되지 않는다.

• $1 \le c \le 11$
• 지역 이름은 알파벳과 숫자로 이루어진 길이 $1$ 이상 $20$ 이하의 문자열이고 서로 다르다
• 각 지역의 가치는 $-1000$ 이상 $1000$ 이하의 정수
• $0 \le m \le 100$
• 도로의 길이는 $1$ 이상 $10000$ 이하의 정수
• $1 \le p \le 10$
• 이동할 수 있는 최대 거리는 $0$ 이상 $1000000$ 이하의 정수
• 출발지와 도착지는 앞에서 주어진 지역 이름 중 하나이고 서로 같을 수도 있다

각 테스트 케이스마다 한 줄에 Case x: v 형식으로 출력한다. $x$는 $1$부터 시작하는 케이스 번호이고, $v$는 얻을 수 있는 가치 합의 최댓값이다. 가치 합에는 출발지와 도착지도 포함한다.

이동할 수 있는 최대 거리 안에서 출발지부터 도착지까지 갈 수 있는 경로가 없으면 $v$ 자리에 Not possible을 출력한다.