시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB37316513141.587%

문제

무토는 여행을 좋아하는 무사입니다. 무토는 관광지에 도착하면, 그곳에서 $1$시간 동안 머무릅니다. 한 곳에서만 있는 것이 심심했던 무토는 다음 질문을 $Q$번 하였습니다.

다음 조건을 만족하며 $s$번 관광지에서 $e$번 관광지로 이동하려고 해. 이때 최소 이동 시간은 몇 분일까?

  • $s$번 관광지에서 $e$번 관광지까지 이동할 때, 하나의 도로만 이용합니다.

무토의 질문을 해결해 주세요.

입력

첫 번째 줄에 일본 관광지의 수 $N$, 도로의 수 $M$, 질문의 수 $Q$가 공백으로 구분되어 주어집니다.

두 번째 줄부터 $M$개의 줄에 걸쳐 도로 정보 $a$, $b$, $c$가 공백으로 구분되어 주어집니다. 이는 $a$번 관광지와 $b$번 관광지 사이에 이동 시간이 $c$분인 양방향 도로가 있음을 의미합니다.

$M+1$번째 줄부터 $Q$개의 줄에 걸쳐 질문 정보 $s$, $e$가 공백으로 구분되어 주어집니다.

출력

 $Q$개의 줄에 걸쳐 문제의 답을 아래와 같이 한 줄에 하나씩 출력해 주세요.

  • 조건을 만족하면서 이동할 수 있다면, 최소 이동 시간을 출력해 주세요.
  • 그렇지 않다면 -1을 출력해 주세요.

제한

  • $1 \leq N \leq 2 \times 10^{5}$
  • $1 \leq M \leq 4 \times 10^{5}$
  • $1 \leq Q \leq 4 \times 10^{5}$
  • $1 \leq a, b \leq N; a \ne b$
  • $1 \leq c \leq 10^{9}$
  • $1 \leq s, e \leq N; s \ne e$
  • 입력으로 주어지는 모든 수는 정수입니다.

예제 입력 1

4 2 3
1 2 3
3 4 2
1 2
3 2
4 2

예제 출력 1

3
-1
-1

예제 입력 2

5 4 2
1 2 3
1 3 3
1 4 3
1 5 3
1 2
1 3

예제 출력 2

3
3