Drifting

You are given a weighted directed graph of $N$ vertices and $M$ edges, with vertices numbered $1$ to $N$ and edges numbered $1$ to $M$. The $i$-th ($1 \le i \le M$) edge connects from vertex $u_i$ to vertex $v_i$ ($u_i < v_i$), and the weight of the edge is $w_i$.

Also, $K$ triplets of integers are given. The $i$-th ($1 \le i \le K$) triplet is $(a_i, b_i, c_i)$ ($a_i < b_i < c_i$).

You start at vertex $1$ and move to vertex $N$ by repeatedly moving along an edge.

In addition, for all $i$ ($1 \le i \le K$), if you move from vertex $a_i$ to vertex $b_i$ directly, we must next move to a vertex other than vertex $c_i$.

Judge whether it is possible to reach vertex $N$. If it is possible to reach, also calculate the minimum sum of the weights of the edges you pass through.

$N$ $M$

$u_1$ $v_1$ $w_1$

$u_2$ $v_2$ $w_2$

$\vdots$

$u_M$ $v_M$ $w_M$

$K$

$a_1$ $b_1$ $c_1$

$a_2$ $b_2$ $c_2$

$\vdots$

$a_K$ $b_K$ $c_K$

If you cannot reach vertex $N$, output $-1$. Otherwise, output the minimum sum of the weights of the edges you pass through.

• All inputs consist of integers.
• $3 \le N \le 2 \times 10^5$
• $0 \le M \le 2 \times 10^5$
• $1 \le u_i < v_i \le N$ ($1 \le i \le M$)
• $i \ne j \Rightarrow (u_i, v_i) \ne (u_j, v_j)$ ($1 \le i, j \le M$)
• $1 \le w_i \le 10^9$ ($1 \le i \le M$)
• $0 \le K \le 2 \times 10^5$
• $1 \le a_i < b_i < c_i \le N$ ($1 \le i \le K$)

In Sample Input 1, the best move is $1 \rightarrow 3 \rightarrow 4$.

In Sample Input 2, the best move is $1 \rightarrow 2 \rightarrow 4 \rightarrow 6 \rightarrow 7$.