Cho một đồ thị có hướng gồm n đỉnh đánh số từ 0 đến n-1 và m cạnh. Mỗi cạnh (u, v) có một trọng số w biểu thị thời gian di chuyển từ đỉnh u đến đỉnh v.

Tồn tại một số nguyên dương k. Tại bất kỳ thời điểm t nào (ngoài trừ thời điểm t = 0), nếu t là bội số của k (tức là t % k = 0), thì tất cả các đỉnh đều không thể đi qua.

Cho hai đỉnh x và y. Nhiệm vụ của bạn là tìm đường đi ngắn nhất từ đỉnh x đến đỉnh y, sao cho không đi qua bất kỳ đỉnh nào vào các thời điểm bị cấm. Lưu ý: Bạn phải di chuyển liên tục và không được dừng lại ở bất kỳ đỉnh nào để đợi.

Input:

• Dòng đầu tiên: bốn số nguyên n, m, k, x, y (1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5, 1 ≤ k ≤ 100, 0 ≤ x, y < n)
• M dòng tiếp theo: mỗi dòng gồm ba số nguyên u, v, w (0 ≤ u, v < n, 1 ≤ w ≤ 10^5), biểu thị một cạnh từ u đến v với trọng số w

Output:

• In ra -1 nếu không thể đi từ đỉnh x đến đỉnh y theo yêu cầu đề bài
• Ngược lại, in ra thời gian ngắn nhất để đi từ đỉnh x đến đỉnh y