Ở hành tinh Orion có ~N~ căn cứ được nối với nhau bởi ~M~ cổng dịch chuyển hai chiều. Nhà thám hiểm Steve muốn chuẩn bị một bộ thẻ năng lượng để có thể đi qua các cổng này. Có tất cả ~K~ loại thẻ, loại thứ ~i~ có giá trị năng lượng ~c_i~.

Mỗi cổng dịch chuyển yêu cầu Steve phải trình ra một số loại thẻ khác nhau. Lưu ý:

• Steve chỉ cần trình ra chứ không mất thẻ.

• Vì vậy, một thẻ có thể dùng lại ở nhiều cổng khác nhau.

• Steve sẽ chọn trước một tập thẻ để mang theo trong suốt chuyến đi.

Một điều đặc biệt là dãy giá trị thẻ thỏa mãn:

~2 \cdot c_{i-1} \le c_i~ ~(2 \le i \le K)~.

Steve muốn chọn tập thẻ có tổng giá trị nhỏ nhất sao cho dù xuất phát từ căn cứ nào, cậu cũng có thể đi thăm tất cả ~N~ căn cứ.

Yêu cầu: Hãy tính tổng giá trị nhỏ nhất của tập thẻ cần mang theo. Nếu không tồn tại cách chọn, in ra ~-1~.

Input

• Dòng đầu gồm ~3~ số nguyên dương ~N,M,K~ ~(N,M,K \le 10^5)~.

• Dòng thứ hai gồm ~K~ số nguyên ~c_1,c_2,\dots,c_K~.

• Mỗi dòng trong ~M~ dòng tiếp theo mô tả một cổng:

  • Ba số ~u_i,v_i,t_i~: cổng nối giữa hai căn cứ ~u_i,v_i~ và cần ~t_i~ loại thẻ;

  • Tiếp theo là ~t_i~ số nguyên dương là chỉ số các loại thẻ cần có.

Output

Ghi ra một số nguyên duy nhất là đáp án. Nếu không thể chọn thỏa mãn, in ra ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

8

Notes

Chọn các thẻ số ~1,2,3~ với tổng giá trị là:

~1+2+5=8~.

Khi đó Steve có thể dùng cổng nối ~1-2~ và ~1-3~ để đi thăm toàn bộ các căn cứ.