Drifting

You are given a weighted directed graph with $N$ vertices and $M$ edges. The $i$-th edge goes from vertex $u_i$ to vertex $v_i$ with weight $w_i$. Every edge satisfies $u_i < v_i$.

You are also given $K$ triples of integers. The $i$-th triple is $(a_i, b_i, c_i)$ with $a_i < b_i < c_i$.

You start at vertex $1$ and move along edges until you reach vertex $N$. If you move directly from $a_i$ to $b_i$, your next move must go to a vertex other than $c_i$.

Determine whether vertex $N$ can be reached. If it can, find the minimum total weight of the edges you pass through.

The first line contains $N$ and $M$. Each of the next $M$ lines contains $u_i$, $v_i$, and $w_i$. The next line contains $K$. Each of the next $K$ lines contains $a_i$, $b_i$, and $c_i$.

If vertex $N$ cannot be reached, print $-1$. Otherwise, print the minimum total weight of the edges you pass through.

• $3 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le u_i < v_i \le N$ for all $i$
• No two edges have the same $(u_i, v_i)$
• $1 \le w_i \le 10^9$
• $0 \le K \le 2 \times 10^5$
• $1 \le a_i < b_i < c_i \le N$ for all $i$

In the first sample, the best route is $1 \rightarrow 3 \rightarrow 4$. In the second sample, the best route is $1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$.