時は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

入出力例

入力例1

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

出力例1

9

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

入力例2

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

出力例2

-1

入力例3

2 2 2
1 1
1 2 2
2 1 3

出力例3

6

入力例4

2 2 2
1 2
1 2 2
2 1 3

出力例4

0

入力例5

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

出力例5

6