Thành phố ~\texttt{QHHOJ}~ đang trong quá trình đổi mới với mục tiêu "Không để ai phải đi xe một mình" , chính vì thế ban quản trị quyết định xây dựng các tuyến xe bus hoàn toàn mới nhằm phục vụ cho nhu cầu sử dụng của người dân. Được biết thành phố bây giờ đang có ~n~ địa điểm đang được xây dựng làm trạm dừng xe và ~m~ con đường một chiều giữa ~2~ thành phố liền kề ~u, v~ (Giữa hai thành phố có thể có nhiều con đường nhưng mỗi con đường chỉ được nối giữa ~2~ thành phố).

Dựa theo kế hoạch, ~D~ tuyến xe bus khác nhau sẽ được xây dựng bởi đội ngũ chuyên nghiệp của CodeTN. Với tầm nhìn nhầm chiến lược và nổi trội của mình anh ta đã phát hiện ra rằng trạm ~C~ là trạm đặc biệt bởi được xây dựng ở giữa trung tâm thành phố ~\texttt{QHHOJ}~, gần với các trung tâm thương mại, trường học,... dẫn đến đây luôn là một trong nhưng trạm có nhu cầu sử dựng cao nhất. Chính vì vậy CodeTN quyết định tất cả các tuyến sắp được xây phải đi qua thành phố này và không được bắt đầu hay kết thúc tại thành phố ~C~, bên cạnh đó còn định nghĩa rằng ~2~ tuyến xe bus được gọi là giống nhau nếu giống nhau điểm đầu và điểm cuối. CodeTN quyết tâm hoàn thành kế hoạch với chi phí nhỏ nhất nhưng vẫn chưa biết phải làm sao, vì vậy hôm nay nhiệm vụ của các bạn là giúp anh ấy hoàn thành kế hoạch của mình một cách tốt nhất.

~\texttt{Input}~

• Dòng đầu tiên là ~4~ số tự nhiên ~n, m, D, C~ (~C \leq n \leq 10 ^ 5; m \leq 5 * 10 ^ 5; D \leq 1000~), lần lượt là số trạm xe bus, số con đường một chiều, số tuyến xe bus phải xây dựng và trạm đặc biệt theo cách nhìn của CodeTN.

• ~m~ dòng tiếp theo mỗi dòng gồm ~3~ số tự nhiên ~u, v, len~ (~u, v \leq n; len \leq 10 ^ 9~), thể hiện rằng có một con đường một chiều từ ~u~ đến ~v~ với độ dài là ~len~.

~\texttt{Output}~

• Một dòng duy nhất là tổng đường đi ngắn nhất tìm được khi xây dựng các tuyến xe bus theo kế hoạch đề ra.
• Nếu không có cách nào xây các tuyến xe bus phù hợp in ra ~-1~.

~\texttt{Subtask}~

• Subtask ~1~ (~40\%~ số điểm) (~n \leq 10 ^ 2; m \leq 10 ^ 4~)
• Subtask ~2~ (~60\%~ số điểm) Không có giới hạn gì thêm)

~\texttt{Sample Input}~

3 4 2 1
1 2 9
3 2 28
2 1 3
2 3 11

~\texttt{Sample Output}~

35