Автомагістралі і король

У Королівстві Флатландія є $n$ міст, позначених числами $1,2,...,n$, і дозволено будувати $m$ двонаправлених автомагістралей.

Між містами $a_i$ та $b_i$ можна побудувати $i$-у магістраль з вартістю $c_i$.

Компанія Flatland Road Company планує побудувати $(n-1)$ дозволених автомагістралей з мінімальними загальними витратами, щоб забезпечити пряме або опосередковане з'єднання між будь-якими двома містами.

Король Флатландії має намір видалити деякі магістралі зі списку дозволених. Він хоче дізнатися мінімальну кількість доріг, які потрібно видалити, щоб загальна вартість строго зросла.

Зверніть увагу, що загальна вартість вважається $+\infty$, якщо після видалення не існує можливості побудувати дійсні $(n-1)$ магістралей. Це також вважається як "загальна вартість строго збільшується".

Вхідні дані

Містить нуль або більше тестів. Для кожного тесту:

Перша рядок містить два цілих числа $n(2\le n\le 50)$ і $m(n-1\le m\le n^2)$. $i$-й з наступних $m$ рядків містить $a_i,b_i,c_i(1\le a_i,b_i\le n,1\le c_i\le 10^9)$.

• Будь-які два міста будуть з'єднані, якщо будуть побудовані всі $m$ дозволених автомагістралей.

• Сума $n$ не перевищує $10^3$.

Вихідні дані

Для кожного тесту виведіть відповідь.

Приклади