В Королевстве Флатландия расположено n городов, обозначенных 1, 2, ..., n, и разрешено строить m двунаправленных автомагистралей.

Между городами ai и bi можно построить i-ую магистраль стоимостью ci.

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

Король Флатландии собирается удалить некоторые магистрали из списка разрешенных. Он хотел бы знать минимальное количество дорог, которые необходимо удалить, чтобы строго увеличить общую стоимость.

Обратите внимание, что общая стоимость считается как +∞, если после удаления не существует действительных (n - 1) магистралей. Это также считается как "общая стоимость строго увеличивается".

Входные данные

Содержит ноль или более тестов. Для каждого теста:

Первая строка содержит два целых числа n (2 ≤ n ≤ 50) и m (n - 1 ≤ m ≤ n2). i-я из следующих m строк содержит ai, bi, ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109).

• Любые два города будут соединены, если будут построены все m разрешенных автомагистралей.
• Сумма n не превышает 103.

Выходные данные

Для каждого теста выведите ответ.