정점이 개이고 간선이 개인 단순 무향 가중 연결 그래프가 주어진다.
두 정점 , 의 최단 거리를 구하는 쿼리를 번 처리하시오.
첫 번째 줄에 정점의 개수 과 간선의 개수 이 공백으로 구분되어 주어진다.
첫 번째 줄부터 개의 줄에 걸쳐 각 줄에 정점 에서 정점 까지의 최단 거리를 출력한다.
두 번째 줄부터 개의 줄에 걸쳐 각 줄에 간선이 잇는 두 정점 , 와 간선의 가중치 가 공백으로 구분되어 주어진다.
번째 줄에 쿼리의 개수 가 주어진다.
번째 줄부터 개의 줄에 걸쳐 각 줄에 최단 거리를 구해야 하는 두 정점 , 가 공백으로 구분되어 주어진다.
