時は30世紀，きつねのしえるは雨を司る神としてKUPC国の降雨量を管理している． KUPC国は $N$ 個の地域に分割されており，しえるはそれぞれの地域にまんべんなく雨を降らさなければならない． しえるは呪文をとなえて雨を降らせる． 呪文は $M$ 種類あり，それぞれ $1$ から $M$ まで番号づけられている． $i$ 番目の呪文には湿潤の地域 $a_i$ と乾燥の地域 $b_i$ とが定められており， $a_i$ 番目の地域には雨が $2$ 降り，$b_i$ 番目の地域には雨が降らず， それ以外の $N-2$ 箇所の地域には雨が $1$ 降る． また，$i$ 番目の呪文を実行するのに $d_i$ 日の日数を要する．

まず，最初に $K$ 個の呪文 $(c_1,...,c_{K})$ が実行される． しえるは，その $K$ 個の呪文が実行された後にいくつかの呪文を実行して，各地域の合計雨量を等しくしたいと思っている． $K$ 個の呪文が実行されてから，各地域の合計雨量を等しくするのに最低何日かかるか出力せよ． ただし，各地域の合計雨量を等しく出来ない場合は -1 を出力せよ．

$N$ $M$ $K$
$c_1$ … $c_{K}$
$a_1$ $b_1$ $d_1$
…
$a_M$ $b_{M}$ $d_M$

制約

• $2 \leq N \leq 10000$
• $1 \leq M \leq 20000$
• $1 \leq K \leq 15$
• $1 \leq c_i \leq M$
• $1 \leq a_i \leq N$
• $1 \leq b_i \leq N$
• $a_i \neq b_i$
• $1 \leq d_i \leq 3$
• 入力値はすべて整数である．

この問題の判定には，30点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

• $K = 1$

入出力例

入力例1Copy

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

出力例1Copy

9

$3,5,7,9,10$番目の呪文を実行すれば9日で各地域に同じ量の雨を降らせる事ができる．

入力例2Copy

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

出力例2Copy

-1

入力例3Copy

2 2 2
1 1
1 2 2
2 1 3

出力例3Copy

6

入力例4Copy

2 2 2
1 2
1 2 2
2 1 3

出力例4Copy

0

入力例5Copy

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

出力例5Copy

6