Masala #0928

Xotira 512 MB Vaqt 1000 ms Qiyinchiligi 60 %
14

  

Sayohat qilmoq

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.


Kiruvchi ma'lumotlar:

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. 


Chiquvchi ma'lumotlar:

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.


Misollar
# input.txt output.txt
1
6 6 7
1 2 2
1 3 3
3 6 3
2 4 2
4 6 2
6 5 1
4
1 2 4 6
Izoh:

Eslatma: Liplandiya mamlakatida siklik yo'l mavjud emas!

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin