Phố đèn đỏ

Ngày nào Minh cũng đạp xe tới trường. Nhờ luyện tập thường xuyên, cậu luôn giữ được vận tốc không đổi $v$. Tìm đường đi ngắn nhất từ nhà tới trường là việc dễ dàng với cậu. Tuy nhiên, cậu nhận thấy mỗi khi đi qua một giao lộ, luôn gặp đèn đỏ:

• ở giao lộ $3$ ngả, cậu phải chờ $1$ giây,
• ở giao lộ $4$ ngả, chờ $2$ giây,
• ở giao lộ $5$ ngả, chờ $3$ giây, và cứ thế, mỗi con đường thêm ở giao lộ làm thời gian chờ tăng thêm $1$ giây.

Nói cách khác, khi đi qua một địa điểm có $k$ con đường nối tới, Minh phải chờ $max(0,k-2)$ giây.

Thành phố có $N$ địa điểm và $M$ con đường hai chiều nối giữa chúng. Hãy tính tổng thời gian ngắn nhất để đi từ địa điểm $s$ tới địa điểm $t$, giả sử Minh gặp đèn đỏ ở mọi giao lộ cậu đi qua. Điểm xuất phát và điểm đích không tính thời gian chờ đèn.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $N$, $M$, $v$: số địa điểm, số con đường và vận tốc đạp xe của Minh (mét/giây).
• $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$, $d_i$: một con đường nối hai địa điểm $a_i$ và $b_i$ với độ dài $d_i$ mét.
• Dòng cuối cùng chứa hai số nguyên $s$ và $t$ ($s\ne t$): địa điểm xuất phát và địa điểm đích.

Dữ liệu đảm bảo đồ thị liên thông.

Dữ liệu ra

In ra thời gian di chuyển ngắn nhất từ $s$ tới $t$ (đơn vị giây), làm tròn tới $6$ chữ số thập phân. Đáp án sai lệch không quá ${10}^{-6}$ (tuyệt đối hoặc tương đối) so với đáp án của ban giám khảo được chấp nhận.

Ràng buộc

• $2\le N\le 2\times {10}^5$
• $1\le M\le min(4\times {10}^5,\frac{N(N+1)}{2})$
• $1\le v\le {10}^3$
• $1\le a_i,b_i\le N$, $a_i\ne b_i$, $1\le d_i\le {10}^6$
• Không có hai con đường nối cùng một cặp địa điểm.

Ví dụ