B. Кактусофобия
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — это связный неориентированный граф без циклов. Реберный кактус — связный неориентированный граф без петель и кратных ребер, в котором каждое ребро лежит не более чем на одном простом цикле.

У Васи есть реберный кактус, в котором каждое ребро покрашено в какой-то цвет.

Вася хочет убрать из кактуса минимальное число ребер так, чтобы получилось дерево. При этом Вася хочет, чтобы количество различных цветов среди оставшихся ребер было максимально. Помогите ему узнать, сколько различных цветов может остаться в графе.

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

В первой строке дано два целых числа n, m (2 ≤ n ≤ 10 000) — количество вершин и ребер в графе Васи соответственно.

В следующих m строках дано по три целых числа u, v, c (1 ≤ u, v ≤ n, u ≠ v, 1 ≤ c ≤ m) — вершины, которые соединяет очередное ребро, и его цвет. Гарантируется, что описанный граф является реберным кактусом.

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

Выведите одно целое число — максимальное количество различных цветов, которое можно оставить в графе.

Примеры
Входные данные
4 4
1 2 4
2 3 1
3 4 2
4 2 3
Выходные данные
3
Входные данные
7 9
1 2 1
2 3 4
3 1 5
1 4 5
4 5 2
5 1 6
1 6 4
6 7 6
7 1 3
Выходные данные
6