어떤 나라에는 \(N\)개의 도시가 있고, 도시들을 잇는 \(M\)개의 양방향 도로가 있다. \(i\)번째 도로는 두 도시 \(a_i\), \(b_i\)를 통행료 \(c_i\)로 잇는다. 같은 도시 쌍을 잇는 도로가 여러 개일 수 있으며, 이 경우 어느 도로든 사용할 수 있다.

여행자들은 한 도시에서 다른 도시로 이동할 때 통행료의 합이 최소가 되는 경로를 택한다. \(Q\)개의 질의가 주어지며, 각 질의는 출발 도시 \(s\)와 도착 도시 \(t\)로 이루어진다. 각 질의에 대해 \(s\)에서 \(t\)로 가는 최소 통행료 합을 출력하여라. 만약 도달할 수 없다면 \(-1\)을 출력한다.

\(1 \le N \le 250\)

\(0 \le M \le 60{,}000\)

\(1 \le c_i \le 1{,}000\)

\(1 \le Q \le 100{,}000\)

첫째 줄에 도시의 수 \(N\)과 도로의 수 \(M\)이 주어진다.

다음 \(M\)개의 줄에 각각 세 정수 \(a_i\), \(b_i\), \(c_i\) (\(1 \le a_i, b_i \le N\), \(a_i \ne b_i\), \(1 \le c_i \le 1{,}000\))가 주어진다.

그 다음 줄에 질의의 수 \(Q\)가 주어지고, 이어서 \(Q\)개의 줄에 각각 두 정수 \(s\), \(t\) (\(1 \le s, t \le N\))가 주어진다.

각 질의에 대해 최소 통행료 합을, 도달할 수 없으면 \(-1\)을 한 줄에 하나씩 출력한다.

riseoj 작성

출처 Original