Vương quốc Atlanta huyền bí có ~n~ thành phố được đánh số từ 1 tới ~n~, ~m~ con đường hai chiều nối trực tiếp các thành phố với nhau, thời gian đi hết con đường thứ ~i~ là ~w_i~ (~1 \le i \le m~) và có ~k~ cánh cửa thần kỳ đặt ở ~k~ thành phố khác nhau.

Nôbita đến Atlanta ban đầu ở thành phố 1 và tất cả các cánh cửa thần kỳ đều đóng, khi Nôbita đặt chân đến thành phố có cánh cửa thần kì thì nó sẽ mở ra, khi một cánh cửa thần kỳ mở ra thì nó giúp Nôbita có thể dịch chuyển tức thời tới một thành phố khác có cánh cửa đã mở trước đó với thời gian là 0. Nôbita muốn gặp Suka, vị thần cai quản Atlanta ra điều kiện: Nếu Nôbita mở được tất cả các cửa thần kỳ thì sẽ được gặp Suka.

Yêu cầu: Hãy tìm thời gian ngắn nhất để Nôbita có thể mở hết tất cả các cánh cửa thần kỳ trong vương quốc biết rằng với ~m~ con đường Nôbita có thể đi từ thành phố bất kỳ đến một thành phố khác.

Dữ liệu

Vào từ tệp văn bản NOBITA.INP

• Dòng đầu chứa hai số nguyên ~n, m~ (~1 \le n \le 10^5~; ~0 \le m \le 2 \times 10^5~);
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~x_i, y_i, w_i~ thể hiện có đường đi trực tiếp giữa hai thành phố ~x_i~ và ~y_i~ với thời gian là ~w_i~ (~1 \le x_i, y_i \le n, x_i \ne y_i, 1 \le w_i \le 10^9~). Giữa hai thành phố có tối đa một đường đi trực tiếp;
• Dòng tiếp theo chứa số nguyên ~k~ (~1 \le k \le n~);
• Dòng cuối chứa ~k~ số nguyên ~u_1, u_2, \ldots, u_k~ là số hiệu của các thành phố có cửa thần kỳ.

Kết quả

Ghi ra tệp văn bản NOBITA.OUT gồm một số nguyên duy nhất thể hiện thời gian ngắn nhất để Nôbita có thể mở hết tất cả các cánh cửa thần kỳ trong vương quốc.

Ví dụ

NOBITA.INP

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

NOBITA.OUT

12

Giải thích: Đường đi có thời gian ngắn nhất là: 1 → 2 (mở cánh cửa thần kì ở 2) → 3 (mở cánh cửa thần kì ở 3) → 2 → 1 → 4 (mở cánh cửa thần kì ở 4). Lúc này đường đi của Nôbita kết thúc (đã mở cả 3 cánh cửa) với thời gian là 12.

Giới hạn

• Có 40% số test tương ứng với 40% số điểm của bài với ~k = n~.
• Có 20% số test tương ứng với 20% số điểm của bài với ~k = 1~.
• Có 20% số test tương ứng với 20% số điểm của bài với ~1 < k \le 4~.
• Có 20% số test tương ứng với 20% số điểm của bài với ~5 \le k < n~.