Krallıq
Nağıl krallığında N şəhər mövcuddur. Bəzi şəhər cütləri yollarla birləşdirilib və eyni şəhər cütünü bir neçə yol birləşdirə bilər. Şəhərlərdən kənarda yollar kəsişmir. Hər bir yolda hər iki istiqamətdə hərəkət etmək mümkündür. Kralın bütün yollardan keçərək heç birini iki dəfə keçmədən səyahət edə bilməsi üçün krallıqda neçə yolun daha tikilməli olduğunu müəyyən etməyə kömək edin. Təbii ki (aşağıdakı nümunəyə baxın), o, hər bir şəhəri ziyarət etmək istəyir. Kralın səyahəti eyni şəhərdə başlayıb bitməlidir.
Giriş məlumatları
Əvvəlcə krallıqda şəhərlərin sayını N (1 ≤ N ≤ 100) və şəhər cütlərinin sayını K (1 ≤ K ≤ 10000) daxil edirsiniz. Sonra K qrupda 3 ədəd daxil edirsiniz: şəhərlərin nömrələri və onları birləşdirən yolların sayı (bütün ədədlər 100-dən çox deyil). Bütün ədədlər boşluqla ayrılıb.
Çıxış məlumatları
Ən az mümkün yol sayını çıxış edin.