전쟁 중인 나라

2050년, 국제 기구가 여러 차례 평화를 지키려 했지만 결국 제3차 세계 대전이 터진다. 산업 기밀과 상업 기밀, 군사 기밀 때문에 모든 나라가 아주 정교한 첩보 조직을 운영하게 되었고, 세계의 모든 도시에는 나라마다 첩보원이 적어도 한 명 있다. 첩보원은 임무 중에 다른 첩보원, 정보원, 본부와 연락해야 한다. 전시에는 안전한 통신 수단이 없으므로 모든 전언을 암호로 보내고, 수신자만 그 뜻을 읽는다.

첩보원이 쓰는 수단은 전시에도 유일하게 돌아가는 우편이다. 도시마다 우체국이 하나 있다. 편지는 목적지 도시의 우체국으로 곧바로 갈 수도 있고, 다른 우체국을 여러 번 거쳐 갈 수도 있다.

도시 $A$의 우체국은 도시 $B$의 우체국과 배달 협정이 있으면 인쇄된 편지를 곧바로 보낼 수 있다. 협정에는 편지가 $A$에서 $B$까지 가는 데 걸리는 시간이 시간 단위로 정해져 있다. 반대 방향에도 협정이 있어야 하는 것은 아니다. $A$와 $B$ 사이에 협정이 없으면 $A$는 필요한 만큼 다른 우체국을 거쳐 편지를 보낸다.

일부 우체국은 위성이나 광섬유 같은 전자 통신으로 이어져 있다. 전쟁 전에는 이 연결이 모든 우체국에 닿아서 편지가 즉시 전달되었다. 전쟁이 시작되면서 나라마다 전자 통신을 통제해, 같은 나라 안의 우체국끼리만 편지를 전자 통신으로, 즉 시간을 전혀 들이지 않고 보낼 수 있다. 우체국 $A$와 $B$는 인쇄된 편지가 $A$에서 $B$로도 전달되고 $B$에서 $A$로도 전달될 때 같은 나라에 있다.

우리 첩보 조직은 세계에 있는 배달 협정을 모두 입수했다. 여러 도시 쌍에 대해 편지를 보내는 최소 시간을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 도시의 수 $N$ ($1 \le N \le 500$)과 배달 협정의 수 $E$ ($0 \le E \le N^2$)가 공백으로 구분되어 주어진다. 도시에는 1번부터 $N$번까지 번호가 붙어 있다.

다음 $E$개의 줄에는 각각 세 정수 $X$, $Y$, $H$ ($1 \le X, Y \le N$, $1 \le H \le 1000$)가 공백으로 구분되어 주어진다. 도시 $X$에서 도시 $Y$로 인쇄된 편지를 보내는 협정이 있고, 그 편지는 $H$시간 뒤에 도착한다는 뜻이다.

그다음 줄에는 질의의 수 $K$ ($0 \le K \le 100$)가 주어진다. 이어지는 $K$개의 줄에는 각각 두 정수 $O$와 $D$ ($1 \le O, D \le N$)가 공백으로 구분되어 주어진다. 질의마다 도시 $O$에서 도시 $D$로 편지를 보내는 최소 시간을 구해야 한다.

$N$과 $E$가 모두 0인 줄이 입력의 끝을 알린다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 $K$개의 줄을 출력한다. $I$번째 줄에는 $I$번째 질의의 최소 시간을 시간 단위 정수로 출력한다. 질의에 주어진 두 도시 사이에 편지를 전달할 방법이 없으면 그 줄에 Nao e possivel entregar a carta를 그대로 출력한다. 따옴표는 출력하지 않는다.

테스트 케이스를 하나 출력한 뒤에는 빈 줄을 하나 출력한다.