문제

정점이 개, 간선이 개인 가중치 그래프가 주어진다. 이 그래프에서 차수가 이상인 정점의 수는 최대 개이다. 임의의 두 정점 사이의 최단거리를 구하는 쿼리를 번 처리하라. 쿼리는 다음의 형식으로 주어진다.

• : 번째 정점과 번째 정점 사이의 최단 경로를 구하여라

주어진 그래프는 자기 자신으로 돌아오는 간선이 없고, 중복된 간선이 없으며, 항상 연결그래프임이 보장된다.

입력

첫째 줄에 , , 가 공백에 걸쳐 주어진다.

두 번째 줄부터 번째 줄까지 간선의 양 끝 정점 , 와 가중치 가 공백에 걸쳐 주어진다.

번째 줄부터 번째 줄까지 각 쿼리에 대한 정보 , 이 공백에 걸쳐 주어진다.

출력

각 쿼리마다 최단 경로의 길이를 한 줄에 걸쳐 출력한다.