Drifting

가중치가 있는 방향 그래프가 주어진다. 정점은 $N$개, 간선은 $M$개이다. $i$번째 간선은 정점 $u_i$에서 정점 $v_i$로 향하며 가중치는 $w_i$이다. 모든 간선은 $u_i < v_i$를 만족한다.

정수 세 개로 이루어진 묶음이 $K$개 주어진다. $i$번째 묶음은 $(a_i, b_i, c_i)$이며 $a_i < b_i < c_i$이다.

정점 $1$에서 출발해 간선을 따라 이동하여 정점 $N$에 도달하려 한다. 정점 $a_i$에서 $b_i$로 바로 이동했다면, 다음에 이동할 정점은 $c_i$가 아니어야 한다.

정점 $N$에 도달할 수 있는지 판단하라. 도달할 수 있다면 지나는 간선 가중치의 합이 최소가 되는 값을 구하라.

첫째 줄에 $N$과 $M$이 주어진다. 이어서 $M$개의 줄에 $u_i$, $v_i$, $w_i$가 주어진다. 다음 줄에 $K$가 주어지고, 이어서 $K$개의 줄에 $a_i$, $b_i$, $c_i$가 주어진다.

정점 $N$에 도달할 수 없으면 $-1$을 출력한다. 그렇지 않으면 지나는 간선 가중치 합의 최솟값을 출력한다.

• $3 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• 모든 $i$에 대해 $1 \le u_i < v_i \le N$
• 서로 다른 $i, j$에 대해 $(u_i, v_i) \ne (u_j, v_j)$
• $1 \le w_i \le 10^9$
• $0 \le K \le 2 \times 10^5$
• 모든 $i$에 대해 $1 \le a_i < b_i < c_i \le N$

첫 번째 예제에서 최선의 이동은 $1 \rightarrow 3 \rightarrow 4$이다. 두 번째 예제에서 최선의 이동은 $1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$이다.