問題文

頂点に $1$ から $N$ 、辺に $1$ から $M$ の番号が付いた $N$ 頂点 $M$ 辺の重み付き有向グラフが与えられます。$i\ (1\leq i \leq M)$ 番目の辺は頂点 $u_i$ から頂点 $v_i$ $(u_i \lt v_i)$ へ張られていて、辺の重みは $w_i$ です。

また、整数の三つ組が $K$ 個与えられます。$i\ (1\leq i \leq K)$ 番目の三つ組は $(a_i,b_i,c_i)\ (a_i < b_i < c_i)$ です。

あなたははじめ頂点 $1$ にいて、辺が張られた頂点に移動することを繰り返して頂点 $N$ に移動したいです。

ただし、全ての $i\ (1\leq i \leq K)$ に対して、頂点 $a_i$ の次に頂点 $b_i$ に移動した場合、次は頂点 $c_i$ 以外の頂点に移動しなくてはなりません。

頂点 $N$ へ移動できるか判定してください。移動できる場合、通る辺の重みの総和の最小値も求めてください。

制約

入力

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

出力

頂点 $N$ へ移動できない場合、-1 を出力せよ。そうでない場合、通る辺の重みの総和の最小値を出力せよ。

サンプル

4 4
1 2 1
1 3 2
2 4 2
3 4 2
1
1 2 4

4

7 8
1 2 5
1 3 2
2 4 1
3 4 1
4 5 6
4 6 2
5 7 1
6 7 1
2
2 4 5
3 4 6

9

3 2
1 2 1
2 3 1
1
1 2 3

-1