Masala #0928

Qulmamat Liplandiya shahriga sayohatga bordi. Bu shaxarda \(1\) dan \(n\) gacha raqamlangan shaxarlar mavjud bo'lib, ikkita shaxarni bog'lovchi yo'l bir tomonlama edi. Qulmamatning \(T\) soat vaqti mavjud bo'lib, u \(T\) soat ichida imkon qadar ko'proq shaxarlarga sayohatni amalga oshirishni istaydi.

Qulmamat \(1\) shaxardan sayohatni boshlab \(n\) shaxarda yakunlamoqchi. Agar ikki shaxarni bog'lab turuvchi yo'l \((u_i, v_i)\) mavjud bo'lsa bu yo'lni u \(t_i\) soatda bosib o'tadi.

Sizning vazifangiz Qulmamat imkon qadar ko'proq shaxarlarga sayohat qilishi uchun \(T\) soatdan oshmagan vaqtda ketma-ket qaysi shaxarlarga borish kerak ekanligini ko'rsatuvchi dastur tuzib berishdan iborat.

Dastlabki satrda \(n,m,T(2\leq n\leq 10000, 1\leq m\leq 10000, 1\leq T\leq 10^6)\) sonlar, mos ravishda shaxarlar soni, yo'llar soni va sayohat uchun Qulmamatda mavjud bo'lgan vaqt.

Kiyingi \(m\) ta satrda \(u_i, v_i, t_i(1\leq u_i, v_i\leq n, 1\leq t_i\leq 10^9)\) uchliklar, bu yerda \((u, v)\) juflik o'rtasida yo'l mavjud va bu yo'lni bosib o'tish uchun \(t\) vaqt ketadi. 

Chiqish faylining dastlabki satrida Qulmamat jami nechta shaxarlarga sayohat qilishini va kiyingi satrda sayohatni qaysi shaxarlarda amalga oshirishi kerak ekanligini ketma-ket probil bilan ajratilgan holda chop eting. Agar bunday yechimlar bir nechta bo'lsa istalganini chop etishingiz mumkun.