Автомагістралі і король#11315
У Королівстві Флатландія є міст, позначених числами 1, 2, ..., n, і дозволено будувати двонаправлених автомагістралей.
Між містами a_i та b_i можна побудувати -у магістраль з вартістю c_i.
Компанія Flatland Road Company планує побудувати (n - 1) дозволених автомагістралей з мінімальними загальними витратами, щоб забезпечити пряме або опосередковане з'єднання між будь-якими двома містами.
Король Флатландії має намір видалити деякі магістралі зі списку дозволених. Він хоче дізнатися мінімальну кількість доріг, які потрібно видалити, щоб загальна вартість строго зросла.
Зверніть увагу, що загальна вартість вважається , якщо після видалення не існує можливості побудувати дійсні (n - 1) магістралей. Це також вважається як "загальна вартість строго збільшується".
Містить нуль або більше тестів. Для кожного тесту:
Перший рядок містить два цілих числа n~(2 \le n \le 50) і m~(n - 1 \le m \le n^2). -й з наступних рядків містить a_i, b_i, c_i~(1 \le a_i, b_i \le n, 1 \le c_i \le 10^9).
Будь-які два міста будуть з'єднані, якщо будуть побудовані всі дозволених автомагістралей.
Сума не перевищує 10^3.
Для кожного тесту виведіть відповідь.
Приклад 1