Kế hoạch xây dựng

Hệ thống giao thông trong một thành phố có \(n\) nút giao thông được đánh số từ \(1\) đến \(n\) và \(m\) tuyến đường hai chiều nối giữa các nút giao thông này. Công ty ABC đã xây dựng một hệ thống \(k\) cửa hàng đặt tại các nút giao thông. Công ty lên kế hoạch xây dựng một kho hàng đặt tại một nút giao thông sao cho khoảng cách từ nơi đặt kho đến cửa hàng xa kho nhất là nhỏ nhất.

Yêu cầu: Xác định vị trí nút giao thông đặt kho hàng sao cho khoảng cách từ nơi đặt kho đến cửa hàng xa kho nhất là nhỏ nhất.

Input

Dữ liệu vào có dạng:

• Dòng thứ nhất chứa ba số nguyên dương \(n, k, m\) (\(1 \le k \le n \le 10^3\), \(1 \le m \le 10^4\));

• Dòng thứ hai chứa \(k\) số nguyên \(a_1, a_2, \ldots, a_k\) tương ứng là vị trí các nút giao thông đặt \(k\) cửa hàng (\(1 \le a_i \le n\), \(a_i \ne a_j\) với mọi \(i \ne j\));

• Dòng thứ \(i\) trong \(m\) dòng tiếp theo chứa ba số nguyên \(u, v, c\) mô tả tuyến đường thứ \(i\) nối hai nút giao thông \(u\) và \(v\) có khoảng cách \(c\) (\(1 \le u, v \le n\), \(u \ne v\), \(1 \le c \le 10^6\)).
  Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách. Dữ liệu vào luôn đảm bảo tìm được kết quả bài toán.

Ràng buộc:

• Có \(40\%\) số test ứng với \(40\%\) số điểm có giá trị \(n \le 10^2\).

• Có \(60\%\) số test ứng với \(60\%\) số điểm có giá trị \(n \le 10^3\).

Output

In ra một số nguyên duy nhất là khoảng cách nhỏ nhất từ nơi đặt kho đến cửa hàng xa kho nhất.

Example

Input:

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

Output:

7

Note

Đặt kho tại nút giao thông \(4\), khoảng cách xa nhất từ nhà kho đến cửa hàng tại vị trí \(5\) là \(7\). Đây là giá trị nhỏ nhất so với các phương án đặt kho tại các vị trí khác.