Minh hằng ngày vẫn đi đến trường bằng xe đạp, do luyện tập nên có thể duy trình vận tốc ~v~ không thay đổi. Việc xác định được đường đi ngắn nhất từ nhà đến trường là dễ dàng đối với Minh. Tuy nhiên, theo quan sát mỗi lần qua ngã ba nếu gặp đèn đỏ thì phải đợi mất 1 giây, ngã tư thì mất 2 giây, tương tự cho ngã năm là 3 giây, sáu, bảy,.. tăng thêm 1 giây cho mỗi giao lộ có tăng thêm đường.

Hãy tính thời gian di chuyển từ địa điểm ~s~ đến địa điểm ~t~ giúp Minh nếu trên đường đi toàn gặp đèn đỏ. Riêng nơi xuất phát và đích đến thì không có bị đèn đỏ.

Thành phố Minh ở gồm ~N~ địa điểm và ~M~ con đường hai chiều nối giữa chúng.

Input:

• Dòng đầu tiên chứa ba số nguyên ~N, M, v~ là số địa điểm, số đường và vận tốc xe đạp của Minh, dữ liệu thỏa ~2 \le N \le 2.0^5; 1 \le M \le 4.10^5; 1 \le v \le 10^3~.

• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, d_i~ là đường nối giữa hai đỉnh ~u_i~ và ~v_i~ với khoảng cách ~d_i~, dữ liệu thỏa ~1 \le u_i, v_i \le N; u_i\neq v_i; 1 \le d_i \le 10^6~.

• Dòng cuối cùng chứa hai số nguyên ~s, t~ là đỉnh xuất phát và đỉnh đến.

Đồ thị tương ứng được cho là liên thông.

Output:

• In ra thời gian di chuyển từ ~s~ đến ~t~ ngắn nhất, kết quả in ra với 6 chữ số sau dấu chấm thập phân.

Example:

exam input 1

5 6 1
1 2 5
2 3 5
1 4 10
4 3 2
3 5 3
4 5 8
1 5

exam output 1

14.000000

exam input 2

3 3 7
1 2 8
2 3 9
1 3 20
1 3

exam output 2

2.428571