Tham quan Điện Biên Phủ

Năm nay trại hè Hùng Vương được tổ chức tại thành phố Điện Biên Phủ. Thành phố này có $n$ địa điểm (đánh số từ $1$ đến $n$) và được nối với nhau bằng $m$ con đường hai chiều để có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác.

Trong số $n$ địa điểm này, có $k$ địa điểm hấp dẫn người du lịch. An là một thí sinh tham dự trại hè và lần đầu tiên được đến thành phố Điện Biên Phủ, nên An muốn thăm tất cả $k$ địa điểm hấp dẫn trên.

Ban đầu An đang ở địa điểm $1$. Khi đi từ địa điểm này đến địa điểm khác sẽ mất một số thời gian di chuyển. Nhưng thật kỳ lạ, An có thể di chuyển tức thời từ địa điểm hấp dẫn đang tham quan hiện tại đến một địa điểm hấp dẫn đã tham quan mà không mất thời gian di chuyển nào. Việc di chuyển tức thời không mất thời gian di chuyển này cho phép An di chuyển nhanh chóng giữa các địa điểm của thành phố.

Yêu cầu: Bạn hãy giúp An tính tổng thời gian di chuyển tối thiểu để tham quan tất cả $k$ địa điểm hấp dẫn. Chú ý rằng ta chỉ quan tâm đến thời gian di chuyển, chứ không quan tâm đến thời gian tham quan tại địa điểm đó và không nhất thiết phải quay trở về địa điểm $1$ khi kết thúc hành trình.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1\le n\le {10}^5$; $0\le m\le {10}^5$) cho biết có bao nhiêu địa điểm và con đường trong thành phố.
• Dòng thứ $i$ trong $m$ dòng tiếp theo chứa ba số nguyên $u_i,v_i,w_i$ ($1\le u_i,v_i\le n$; $u_i\ne v_i$; $1\le w_i\le {10}^9$) mô tả một con đường hai chiều nối hai địa điểm $u_i,v_i$ và thời gian cần thiết để đi từ địa điểm này đến địa điểm kia bằng con đường này là $w_i$. Hai địa điểm bất kỳ được nối với nhau không quá một con đường. Dữ liệu đảm bảo rằng có thể đi từ bất kỳ địa điểm nào đến bất kỳ địa điểm nào khác.
• Dòng tiếp theo chứa số nguyên $k$ ($1\le k\le n$) là số địa điểm hấp dẫn.
• Dòng tiếp theo chứa $k$ số nguyên phân biệt $p_1,p_2,\dots ,p_k$ ($1\le p_i\le n$) là các địa điểm hấp dẫn.

Dữ liệu ra

In ra một số nguyên duy nhất là thời gian di chuyển tối thiểu để An tham quan tất cả các địa điểm hấp dẫn. Chú ý rằng thứ tự tham quan các địa điểm hấp dẫn là tùy ý.

Ràng buộc

• $1\le n\le {10}^5$; $0\le m\le {10}^5$.
• $1\le u_i,v_i\le n$; $u_i\ne v_i$; $1\le w_i\le {10}^9$; hai địa điểm bất kỳ được nối với nhau không quá một con đường; đồ thị liên thông.
• $1\le k\le n$; các $p_i$ phân biệt, $1\le p_i\le n$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($10\%$ số test): $k=1$.
• Subtask 2 ($10\%$ số test): $k=n$.
• Subtask 3 ($20\%$ số test): $1\le n\le 10$; $0\le m\le 10$; $1\le w_i\le {10}^2$; $1<k<n$.
• Subtask 4 ($20\%$ số test): $1\le n\le {10}^2$; $0\le m\le {10}^2$; $1\le w_i\le {10}^5$; $1<k<n$.
• Subtask 5 ($20\%$ số test): $1\le n\le {10}^3$; $0\le m\le {10}^3$; $1<k<n$.
• Subtask 6 ($20\%$ số test): không có ràng buộc gì thêm.

Ví dụ