Bài toán định tuyến kèm theo chất lượng dịch vụ bảo đảm trong các ứng dụng đa phương tiện như tuyến tính hình ảnh và âm thanh theo yêu cầu là vấn đề thời sự trong những năm gần đây. Trong bài toán này, chúng ta quan tâm đến độ trễ của các đường truyền tin.

Công ty cung cấp dịch vụ mạng ~\textbf{ESI}~ vừa thiết lập một mạng truyền thông giữa các điểm cung cấp dịch vụ và khách hàng, bao gồm ~n~ nút và ~m~ kênh nối trực tiếp một chiều giữa hai nút. Các nút được đánh số từ ~1~ đến ~n~, trong đó nút ~1~ là nút nguồn. Các kênh nối được đánh số từ ~1~ đến ~m~. kênh nối thứ ~i~ cho phép truyền tin (một chiều) từ nút ~u_i~ tới nút ~v_i~ và có độ trễ là ~c(u_i, v_i)~. Có không quá một kênh truyền tin từ một nút đến một nút khác. Một đường truyền tin từ nút nguồn đến nút ~t~ được biểu diễn dưới dạng một dãy liên tiếp các chỉ số cảu các nút, xuất phát từ ~1~ và kết thúc tại ~t~. Dộ trễ của đường truyền tin được định nghĩa là tổng độ trễ của các kênh nối trực tiếp trên đường truyền tin đó. Để khảo sát các đường truyền tin từ nút nguồn đến một nút ~i~ trong mạng, công ty ~\textbf{ESI}~ xác định ~C_{\text{min}}~ là độ trễ nhỏ nhất trong tất cả các độ trễ của các kênh trong mạng và ~T_{\text{min}}~ là độ trễ của đường truyền tin từ nút nguồn đến nút ~t~ với độ trễ nhỏ nhất. Để đảm bảo dịch vụ đường truyền với chất lượng cao, đường truyền tin từ nút nguồn đến nút ~t~ phải thỏa mãn điều kiện ~\textbf{QoS}~ (Quality of Service) sau đây: độ trễ của đường truyền tin phải nhỏ hơn hoặc bằng tổng số ~T_{\text{min}} + C_{\text{min}}~ Sau đó ~\textbf{ESI}~ sắp xếp tất cả các đường truyền tin từ nút nguồn đến nút ~t~ thỏa mãn điều kiện ~\textbf{QoS}~ theo thứ tự từ điển. Theo định nghĩa của công ty ~\textbf{ESI}~, đường truyền tin ~(x_1, x_2, .., x_p)~ được gọi là có thứ tự từ điển nhỏ hơn đường truyền tin ~(y_1, y_2, ...y_q)~ nếu:

• hoặc ~x_1 < y_1~
• hoặc là ~p < q~ và ~x_i = y_i~ với mọi ~i = 1, 2,.., p~
• hoặc là tồn tại một chỉ số ~u~ ~(1 < u \leq p)~ sao cho ~x_i = y_i~ với mọi ~i = 1, 2, .. u - 1~ và ~x_u < y_u~.

Yêu cầu

Cho trước số nguyên dương ~k~, hãy tìm đường truyền tin từ ~1~ đến ~t~ thỏa mãn điều kiện ~\textbf{QoS}~ thứ ~k~ trong thứ tự từ điển.

Input

Dòng đầu tiên chứa ~4~ số nguyên dương ~n~, ~m~, ~t~, ~k~ ~(k \leq 10^9)~.

Dòng thứ ~i~ trong số ~m~ dòng tiếp theo ghi ba số nguyên dương ~u_i, v_i, c(u_i, v_i)~ lần lượt là chỉ số đầu, chỉ số cuối và độ trễ cuả kênh thứ ~i~. Độ trễ của các kênh là nhỏ hơn ~100~.

Output

Ghi ra ~-1~ nếu không tìm được đường truyền tin thỏa mãn yêu cầu đặt ra, trái lại cần ghi thông tin về đường truyền tin tìm được bao gồm:

• Dòng đầu ghi số nguyên dương ~s~ là số lượng nút trên đường truyền tìm được;
• Dòng thứ hai ghi ~s~ số lần lượt là chỉ số của các nút theo thứ tự mà đường truyền tìm được đi qua, bắt đầu từ nút ~1~ kết thúc ở nút ~t~.

Giới hạn

• ~30\%~ số test có ~n \leq 10~.
• Có ~30\%~ số test khác có ~n \leq 100~.
• Có ~40\%~ số test còn lại ~n \leq 10^3, m \leq 10^5~.

Ví dụ

Input

7 8 7 2
1 2 1
1 5 1
2 3 1
2 4 1
3 7 2
4 7 2
5 6 1
6 7 1

Output

4
1 2 4 7

Nguồn bài: VOI 2014