Chất lượng dịch vụ

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ư truyền 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 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ủa các nút, xuất phát từ $1$ và kết thúc tại $t$. Độ 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 $t$ trong mạng, công ty ESI xác định $C_{min}$ là độ trễ nhỏ nhất trong tất cả các độ trễ của các kênh trong mạng và $T_{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 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_{min}+C_{min}$. Sau đó 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 QoS theo thứ tự từ điển. Theo định nghĩa của công ty ESI, đường truyền tin $(x_1,x_2,\dots ,x_p)$ được gọi là có thứ tự từ điển nhỏ hơn đường truyền tin $(y_1,y_2,\dots ,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,\dots ,p$;
• hoặc là tồn tại một chỉ số $u$ ($1<u\le p$) sao cho $x_i=y_i$ với mọi $i=1,2,\dots ,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 QoS thứ $k$ trong thứ tự từ điển.

Dữ liệu vào

• Dòng đầu tiên chứa bốn số nguyên dương $n$, $m$, $t$, $k$ ($k\le {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ễ của kênh thứ $i$. Độ trễ của các kênh là nhỏ hơn $100$.

Dữ liệu ra

In 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 in ra 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$.

Ràng buộc

• $2\le n\le 1000$; $1\le m\le {10}^5$; $2\le t\le n$; $1\le k\le {10}^9$.
• $1\le u_i,v_i\le n$, $u_i\ne v_i$; có không quá một kênh từ một nút đến một nút khác.
• $1\le c(u_i,v_i)<100$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $n\le 10$.
• Subtask 2 ($30\%$ số điểm): $n\le 100$.
• Subtask 3 ($40\%$ số điểm): $n\le {10}^3$, $m\le {10}^5$.

Mỗi subtask gồm nhiều test, mỗi test được chấm điểm riêng.

Ví dụ