34671번 - 무토의 일본 여행

문제

무토는 여행을 좋아하는 무사입니다. 무토는 관광지에 도착하면, 그곳에서 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$
• 입력으로 주어지는 모든 수는 정수입니다.

노트