최적 경로와 쿼리

여러분은 $N$개의 버스 정류장과 $M$개의 셔틀버스가 있는 마을의 길찾기 서비스를 개발하려고 한다.

$i$번째 셔틀버스는 $u_i$번 정류장과 $v_i$번 정류장 사이를 오고 가는 버스다. 편도로 이동할 때마다 $t_i$만큼의 시간이 걸리며, 두 정류장 외의 다른 정류장에서는 멈추지 않는다.

버스를 갈아타는 것은 매우 귀찮은 일이므로, 출발 지점과 도착 지점이 주어지면 최대 3개의 버스만 이용해 이동하는 가장 짧은 경로를 구해야 한다. 3개 이하의 버스로는 이동할 수 없는 경우도 있다. 이때는 사용자에게 자가용이나 택시 이용을 권하는 메시지를 출력한다.

서비스는 다음 요청을 처리한다.

• $s$ $e$: $s$번 정류장에서 $e$번 정류장으로 최대 3개의 버스만 이용해 이동할 때 필요한 소요 시간의 최솟값을 출력한다. 이동할 수 없다면 -1을 출력한다.

버스를 기다리거나 환승하는 시간은 생각하지 않는다. 버스의 이동 시간만 센다.

첫째 줄에 버스 정류장의 개수 $N$, 셔틀버스의 개수 $M$, 처리해야 하는 요청의 개수 $Q$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 50\,000$, $1 \leq M \leq 50\,000$, $1 \leq Q \leq 50\,000$)

둘째 줄부터 $M$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 셔틀버스의 정보 $u_i$, $v_i$, $t_i$가 공백으로 구분되어 주어진다. ($1 \leq u_i, v_i \leq N$, $1 \leq t_i \leq 50\,000$, $u_i \neq v_i$) 오고 가는 정류장이 같은 버스가 여러 대 주어지지 않는다.

다음 $Q$개의 줄에 걸쳐 요청의 정보 $s$, $e$가 공백으로 구분되어 한 줄에 하나씩 주어진다. ($1 \leq s, e \leq N$, $s \neq e$)

요청의 결과를 한 줄에 하나씩 차례대로 출력한다.