25504번 - 최적 경로와 쿼리

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

$i$번째 셔틀버스는 $u_i$번 정류장과 $v_i$번 정류장 사이를 오고 가는 버스다. 편도로 이동할 때마다 $t_i$ 만큼의 시간이 걸리며, $u_i$와 $v_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$)

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