Задача K. Равнозначный перекресток ≡

Условие

В Графоляндии вся транспортная сеть представлена в виде неориентированного графа на n вершинах, пронумерованных от 1 до n. В Графоляндии есть k дорог, i-я дорога соединяет u_i-ю и v_i-ю вершины и имеет покрытие под номером c_i.

В Графоляндии существует определение перекрестка. Перекресток — набор из i-й вершины и всех входящих в нее дорог, причем количество дорог должно быть больше 2. Равнозначный перекресток — перекресток, все дороги которого имеют одинаковые покрытия.

Определите количество равнозначных перекрестков в Графоляндии.

Формат входных данных

В первой строке вводятся числа n и k — количество вершин и дорог соответственно (2 ≤ n ≤ 10⁵, 1 ≤ k ≤ 5 * 10⁵).

Далее вводится k строк, в i-й строке вводятся числа u_i, v_i и c_i — вершины, которые соединяет дорога, и вид покрытия дороги (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ c_i ≤ 10⁹).

Формат выходных данных

Выведите натуральное число — количество равнозначных перекрестков в Графоляндии.

Примеры тестов

7 7
1 2 6
2 3 6
2 4 6
3 5 5
4 5 5
5 6 5
5 7 5

2