Автомагистральlər və kral#11315
Flatlandiya Krallığında şəhər var, bunlar 1, 2, ..., n ilə işarələnib və iki tərəfli avtomagistral tikməyə icazə verilir.
Şəhərlər a_i və b_i arasında -ci magistralı c_i qiymətinə tikmək mümkündür.
Flatland Road Company, hər hansı iki şəhəri birbaşa və ya dolayı yolla birləşdirmək üçün ən az ümumi xərclə (n - 1) icazə verilən avtomagistral tikməyi planlaşdırır.
Flatlandiyanın kralı, icazə verilən magistrallar siyahısından bəzi magistralları silməyi düşünür. O, ümumi xərci ciddi şəkildə artırmaq üçün neçə yolun silinməsinin lazım olduğunu bilmək istəyir.
Qeyd edək ki, əgər silinmədən sonra etibarlı (n - 1) magistral mövcud deyilsə, ümumi xərc kimi hesab olunur. Bu da "ümumi xərc ciddi şəkildə artır" kimi qəbul edilir.
Sıfır və ya daha çox testdən ibarətdir. Hər bir test üçün:
Birinci sətir iki tam ədəd n~(2 \le n \le 50) və m~(n - 1 \le m \le n^2) ehtiva edir. Növbəti sətirdən -ci sətir a_i, b_i, c_i~(1 \le a_i, b_i \le n, 1 \le c_i \le 10^9) ehtiva edir.
Bütün icazə verilən avtomagistrallar tikilərsə, istənilən iki şəhər birləşdiriləcək.
-lərin cəmi 10^3-ü keçmir.
Hər bir test üçün cavabı yazın.
Nümunə 1