Maraqlı ekskursiya#8260
Flantlandiyada n şəhər var və bu şəhərlər m tək istiqamətli yollarla birləşdirilib.
Turizm şirkəti Flantlandiyanın yollarında mənzərəli bir dövrü marşrut hazırlamaq istəyir. Bu marşrut eyni şəhərdə başlayıb bitməli, yolların istiqamətinə uyğun hərəkət edərək aralıq şəhərləri ziyarət etməlidir. Marşrut bir şəhəri bir neçə dəfə ziyarət edə bilər, lakin hər yoldan yalnız bir dəfə keçməlidir.
Hər yolun mənzərə tipi var və bu, 1-dən m-ə qədər olan bir ədədlə göstərilir. Marşrutun mənzərəli olması üçün ardıcıl iki yol fərqli mənzərə tipinə malik olmalıdır. Bu tələb marşrutun ilk və son yolu üçün də keçərlidir ki, istənilən şəhərdən səyahətə başlamaq mümkün olsun.
Şirkətə bu kriteriyalara uyğun bir marşrut hazırlamaqda kömək edin və ya belə bir marşrutun mümkün olmadığını müəyyənləşdirin.
Giriş bir neçə testdən ibarətdir. İlk sətirdə T ədədi var — testlərin sayı (1 ≤ T ≤ 10^5).
Hər testin təsviri birinci sətirdə iki tam ədəd n və m — şəhərlərin və yolların sayı (2 ≤ n, m ≤ 2 * 10^5). Növbəti m sətir hər biri üç tam ədəd ehtiva edir və yolları u[i], v[i], c[i] formatında təsvir edir — i-ci yolun başladığı şəhər, bitdiyi şəhər və mənzərə tipi (1 ≤ u[i], v[i] ≤ n; 1 ≤ c[i] ≤ m; u[i] ≠ v[i]).
Bütün testlər üzrə n cəmi 2 * 10^5-i keçmir. Bütün testlər üzrə m cəmi 2 * 10^5-i keçmir.
Hər test üçün cavabı verin.Əgər axtarılan marşrut mövcud deyilsə, «-1» çıxış edin. Əks halda, k ədədini çıxış edin — marşrutun uzunluğu (2 ≤ k ≤ m). Növbəti sətirdə k ədəd e1, e2, ..., ek — marşrutda gedilən yolların nömrələrini ardıcıllıqla çıxış edin. Bütün ei nömrələri fərqli olmalıdır. Əgər uyğun marşrutlar bir neçədirsə, onlardan hər hansı birini çıxış edə bilərsiniz.
Nümunə 1