Thành phố \(XYZ\) được xây dựng với \(N\) khu vực và \(M\) con đường hai chiều. Các khu vực được đánh số tương đương với chất lượng cơ sở vật chất và mức sống (tức chỉ số càng cao thì khu vực càng tốt). Mỗi khu vực có một trường học. Đường thứ \(𝑖\) sẽ kết nối khu vực \(u_i\) và khu vực \(v_i\) với độ dài \(w_i\).

Trên toàn thành phố \(XYZ\) có \(K\) học sinh, học sinh \(j\) sẽ sống ở khu vực \(p_j\). Tuy nhiên, trong giai đoạn đầu của cải cách, di chuyển giữa các khu vực còn hạn chế. Học sinh sẽ chọn trường ở khu vực có chỉ số lớn nhất có thể mà không vượt quá khoảng cách \(X\) tính từ nhà học sinh (Một trường có thế có nhiều học sinh).

Chính quyền thành phố \(XYZ\) muốn khảo sát xem trường học có chỉ số bé nhất mà một trong \(K\) học sinh là trường tại khu vực bao nhiêu?.

Yêu cầu: Hãy cho biết trường học có chỉ số bé nhất trong trường hợp tất cả học sinh chọn trường với chỉ số lớn nhất có thể.

Input

• Dòng đầu tiên gồm các số nguyên \(N,M,K,X(1 ≤ K ≤ N ≤ 10^5,0 ≤ M ≤ 10^5,0 ≤ X ≤ 10^{12} )\) là số lượng khu vực, số đường kết nối giữa các thành phố, số lượng học sinh và khoảng cách tối đa mà học sinh có thể di chuyển.

• Dòng thứ \(i\) trong \(M\) dòng tiếp theo, mỗi dòng gồm 3 số nguyên \(u_i, v_i, w_i (1 ≤ u_i, v_i ≤ N,0 ≤w_i ≤ 10^9,1 ≤ i ≤ M)\) miêu tả một đường đi hai chiều từ \(u_i\) đến \(v_i\) có độ dài \(w_i\).

• Dòng tiếp theo gồm \(K\) số \(p_j (1 ≤ p_j ≤ N,1 ≤ j ≤ K)\) là khu vực nhà của học sinh thứ \(j\).

Output

• Một dòng duy nhất là chỉ số của thành phố tìm được.

Ràng buộc:

• Có 40% số test tương đương 40% số điểm thỏa mãn: \(K = 1.\)

• Có 30% số test tương đương 30% số điểm thỏa mãn: \(K ≤ N ≤ 1000,M ≤ 2000.\)

• Có 30% số test tương đương 30% số điểm thỏa mãn: Không có điều kiện gì thêm.

Sample Input

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

sample Output

3