또 다른 최단 경로 질의

평면 그래프는 간선끼리 끝점에서만 만나도록 평면 위에 그릴 수 있는 그래프이다. 즉, 어떤 두 간선도 서로 교차하지 않는다. 이러한 그림을 평면 그래프 또는 평면 임베딩이라고 한다. 형식적으로는 각 정점을 평면 위의 한 점에 대응시키고, 각 간선을 양 끝 정점에 대응하는 점을 끝점으로 하는 평면 곡선에 대응시킨다. 모든 곡선은 끝점을 제외하고 서로 겹치지 않는다.

정점 $n$개와 간선 $m$개로 이루어진 무방향 평면 그래프가 주어진다. 정점은 $1, 2, \ldots, n$으로 번호가 매겨져 있다. $i$번째 간선은 정점 $u_i$와 $v_i$를 잇고, 길이는 $w_i$이다.

질의 $q$개가 주어진다. $i$번째 질의에서는 정수 $s_i$와 $t_i$가 주어진다. 정점 $s_i$에서 정점 $t_i$까지 가는 경로 중 간선을 최대 3개만 사용하는 경로의 최단 길이를 구하라. 그런 경로가 없는지도 판단하라.

첫 줄에 정점 수 $n$과 간선 수 $m$이 주어진다 ($2 \leq n \leq 10^6$, $1 \leq m \leq 10^6$).

이어지는 $m$개 줄의 $i$번째 줄에는 정수 $u_i$, $v_i$, $w_i$가 주어진다 ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq w_i \leq 10^8$). 두 정점을 잇는 간선은 최대 하나이다. 그래프는 평면 그래프임이 보장된다.

다음 줄에는 질의 수 $q$가 주어진다 ($1 \leq q \leq 10^6$).

이어지는 $q$개 줄의 $i$번째 줄에는 정수 $s_i$와 $t_i$가 주어진다 ($1 \leq s_i, t_i \leq n$, $s_i \neq t_i$).

각 질의마다 간선을 최대 3개 사용하는 최단 경로의 길이를 한 줄에 출력한다. 그런 경로가 없으면 -1을 출력한다.