Kefirçik çatdırılması
Müntəzəm keçirilən Qalaktikalararası Yay Kompüter Məktəbi (QYKM) zamanı təşkilatçılar kefirin çatdırılması məsələsi ilə üzləşdilər. Problem ondadır ki, kefir 1 nömrəli planetdə istehsal olunur, lakin şagirdlər n nömrəli planetdə yaşayırlar. Bu səbəbdən kefirin çatdırılması çox vaxt aparır və kefir xarab olur.
Xoşbəxtlikdən, "Berendey-Ekspres" qalaktik nəqliyyat sistemi yeni kefir boru xətləri tətbiq edir ki, bu da kefiri köhnə modellərin sürətindən iki dəfə artıq sürətlə ötürməyə imkan verir. Yəni, istənilən planetdən istənilən planetə köhnə kefir boru xətləri ilə kefir iki ilə, yeni xətlərlə isə bir ilə çatır.
Aydındır ki, bu innovativ texnologiyalardan istifadə etməmək günah olardı. Buna görə də QYKM direktoru sizdən mövcud kefir boru xətləri (həm yeni, həm də köhnə) haqqında məlumatlara əsaslanaraq 1 nömrəli planetdən n nömrəli planetə ən sürətli yolu tapacaq bir proqram yazmağınızı xahiş etdi.
Giriş verilənləri
Giriş faylının ilk sətirində iki tam ədəd n və m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 100000) - planetlərin sayı və kefir boru xətlərinin sayı verilir. Növbəti m sətirdə isə təbii ədədlər üçlüyü u_i, v_i və c_i verilir. Burada u_i və v_i ədədləri i-ci kefir boru xətti ilə birləşdirilən planetlərin nömrələrini, c_i (c_i=1 və ya c_i=2) isə kefirin bir planetdən digərinə i-ci kefir boru xətti ilə ötürülməsi üçün lazım olan illərin sayını göstərir. Giriş faylında planetlər birləşdirilir və kefir boru xətləri hər iki istiqamətdə ötürülə bilər.
Çıxış verilənləri
Çıxış faylında bir ədəd - 1 nömrəli planetdən n nömrəli planetə kefirin çatdırılması üçün lazım olan illərin sayını göstərmək lazımdır. Əgər çatdırılma mümkün deyilsə, çıxış faylında "-1" yazılmalıdır.