Vương quốc JOI có \(N\) thị trấn, được nối với nhau bằng \(M\) con đường hai chiều. Có trung tâm mua sắm tại \(K\) thị trấn; người dân đi theo các con đường đến một trong những thị trấn đó để mua sắm.

Tùy vào vị trí ngôi nhà, người dân có thể phải đi một quãng đường rất dài để mua sắm, gây nhiều bất tiện. Để nắm rõ tình hình, nhà vua muốn biết khoảng cách ngắn nhất từ nhà đến một thị trấn có trung tâm mua sắm có thể lớn đến mức nào. Nhà có thể được xây ở giữa một con đường (xem giải thích ví dụ 1), khiến việc khảo sát trở nên rất khó khăn. Vì vậy, nhà vua nhờ bạn, một lập trình viên tài giỏi, viết chương trình thực hiện cuộc khảo sát này.

Yêu cầu

Cho thông tin về các con đường và các thị trấn có trung tâm mua sắm, hãy tìm giá trị lớn nhất của khoảng cách ngắn nhất từ một điểm trên đường đến một thị trấn có trung tâm mua sắm. Xét tất cả các điểm trên đường, kể cả hai đầu mút. Có thể bỏ qua khoảng cách di chuyển bên trong mỗi thị trấn.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa ba số nguyên \(N,M,K\), cách nhau bởi dấu cách, lần lượt là số thị trấn, số con đường và số thị trấn có trung tâm mua sắm. Các thị trấn được đánh số \(1,2,\ldots,N\).
• \(M\) dòng tiếp theo mô tả các con đường. Dòng \(i+1\) (\(1\le i\le M\)) chứa ba số nguyên \(a_i,b_i,l_i\), cách nhau bởi dấu cách, cho biết con đường thứ \(i\) nối thị trấn \(a_i\) với thị trấn \(b_i\) và có chiều dài \(l_i\). Hai đầu của một con đường không cùng thuộc một thị trấn. Giữa hai thị trấn bất kỳ có nhiều nhất một con đường nối trực tiếp. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác bằng cách đi qua một số con đường.
• \(K\) dòng tiếp theo mô tả vị trí các trung tâm mua sắm. Dòng \(i+M+1\) (\(1\le i\le K\)) chứa một số nguyên \(s_i\), cho biết thị trấn \(s_i\) có trung tâm mua sắm. Các giá trị \(s_1,\ldots,s_K\) đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên: giá trị lớn nhất của khoảng cách ngắn nhất đến một thị trấn có trung tâm mua sắm, sau khi làm tròn đến số nguyên gần nhất. Nếu phần thập phân bằng \(0.5\), làm tròn lên.

Ràng buộc

• \(2\le N\le3000\).
• \(1\le M\le100000=10^5\).
• \(1\le K\le N\).
• \(1\le a_i,b_i\le N\) và \(a_i\ne b_i\) với mọi \(1\le i\le M\).
• \(1\le l_i\le1000\) với mọi \(1\le i\le M\).
• \(1\le s_i\le N\) với mọi \(1\le i\le K\).
• Giới hạn thời gian: \(0.5\) giây. Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) nhóm dữ liệu, mỗi nhóm \(10\) điểm. Mỗi nhóm gồm nhiều bộ dữ liệu; chỉ nhận được điểm của nhóm nếu trả lời đúng tất cả các bộ dữ liệu trong nhóm đó.

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(K=1\).

Ví dụ

3 3 1
1 2 1
2 3 1
3 1 1
1

2

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

3