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$.