Goku và Bulma đang trên đường tìm kiếm 7 viên ngọc rồng để cứu người bạn của mình. Goku đã có một số lượng ngọc rồng nhất định và phải tìm thêm ~K~ viên nữa. Khu vực Goku phải tìm kiếm gồm ~N~ thành phố và ~M~ con đường hai chiều nối liền các thành phố với nhau, con đường thứ ~i~ nối liền thành phố ~u_i~ với thành phố ~v_i~ và tốn thời gian di chuyển là ~w_i~. Trong đó các viên ngọc rồng nằm rải rác trong ~K~ thành phố. Nhờ vào radar của mình mà Bulma đã xác định được hết vị trí các viên ngọc rồng nằm ở thành phố nào.

Ban đầu Goku xuất phát từ thành phố 1, hãy giúp cậu ấy xác định thời gian ngắn nhất sao cho thu thập đủ ~K~ viên ngọc rồng để giải cứu bạn mình.

Lưu ý: Goku chỉ cần đến thành phố có ngọc rồng, thời gian lấy ngọc rồng không đáng kể.

Yêu cầu: Tìm thời gian ngắn nhất để Goku thu thập đủ ~K~ viên ngọc rồng.

Input

• Dòng đầu tiên gồm 3 số nguyên dương ~N, K, M~ (~2 \le N \le 5000; 1 \le K \le \min(7, N - 1); M \le 10000~) – Tương ứng là số thành phố, số lượng ngọc rồng phải tìm và số con đường trong thành phố.
• Dòng thứ 2 gồm ~K~ số nguyên ~p_i~, số nguyên thứ ~i~ biểu diễn vị trí của viên ngọc rồng thứ ~i~ và không có 2 viên ngọc rồng nào nằm cùng vị trí (~2 \le p_i \le N~).
• ~M~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~u_i, v_i, w_i~ tương ứng là có thể di chuyển từ ~u_i~ đến ~v_i~ trong thời gian ~w_i~.

Output

• Gồm một dòng chứa kết quả của bài toán.

Sample Input 1

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

Sample Output 1

4