Sau khi làm nhiệm vụ cho nhóm C.R.A.S.H, thì giờ đây CJ đã không còn làm được gì, cả không thể về lại nơi cũ vì sẽ bị nhóm này truy sát. Trong lúc CJ đang đi quanh quẩn nơi đây thì vô tình gặp Catalina và cô gái này rất là hám tiền. CJ và Catalina bắt tay với nhau, và Catalina nhờ CJ giúp một công việc: Cướp hết ngân hàng nhỏ ở các khu vực nông thôn.

Ở vùng nông thôn San Andreas có \(N\) địa điểm, trong đó có \(K\) địa điểm là ngân hàng, đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, đánh số từ \(1\) tới \(M\), con đường thứ \(i\) có độ dài là \(L_{i}\). Catalina muốn CJ tìm đường đi sao cho xuất phát từ một ngân hàng, cướp hết tất cả \(K\) ngân hàng, mỗi con đường và một địa điểm có thể được đi qua nhiều lần, và độ dài đường đi là ngắn nhất có thể. Đảm bảo hai ngân hàng khác nhau bất kì đều có đường đi.

Yêu cầu: Hãy tìm ra cho CJ và Catalina độ dài đường đi ngắn nhất trên.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(N,M,K\) thể hiện số địa điểm, số con đường hai chiều, số ngân hàng.
• Dòng tiếp theo chứa \(K\) số \(a_{1},a_{2},…,a_{K}\) là số hiệu của các địa điểm là ngân hàng.
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(u_{i},v_{i}, L_{i}\) thể hiện có đường nối trực tiếp \(u_{i},v_{i}\) và độ dài là \(L_{i}\).

Output

• Ghi ra độ dài đường đi ngắn nhất.

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 2.10^{5}\)
• \(1 \leq K \leq 18\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{3}\), \(M \leq 2.10^{3}\), \(K \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^{5}\), \(M \leq 2.10^{5}\), \(K \leq 10\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

4