Трикутники#6196

Трикутники

1 секунда

64 мегабайти

Середня

$N$ цвяхів забито в стіну. Деякі пари цвяхів з'єднані дротами, можливо, кількома. Ви можете припустити, що немає дротів, які з'єднують цвях із самим собою. Кожен дріт має колір: білий, синій або червоний. Ми кажемо, що три дроти утворюють трикутник, якщо є цикл, що з'єднує три цвяхи. Ми називаємо трикутник багатокольоровим, якщо він утворений дротами трьох різних кольорів.

Напишіть програму для обчислення кількості багатокольорових трикутників для заданого списку дротів.

Вхідні дані

Перша строка вхідного файлу містить два числа, розділені пробілом: $N$ і $M$ ( $2 \leq N \leq 1000$ 2 \le N \le 1000, $0 \leq M \leq 3000$ 0 \le M \le 3000) — кількість цвяхів і кількість дротів. Кожна з наступних $M$ строк містить три цілі числа: номери цвяхів, які з'єднані дротом, і колір цього дроту. Колір вказується цілими числами $1$ , $2$ або $3$ .

Вихідні дані

Вихідний файл повинен містити одне ціле число — кількість багатокольорових трикутників.

Приклади

Приклад 1

Примітка

Багатокольорові трикутники утворені наступними трійками дротів:

$(1, 3, 1)$ (1,3,1), $(3, 4, 2)$ (3,4,2), $(1, 4, 3)$ (1,4,3);
$(1, 3, 1)$ (1,3,1), $(3, 4, 2)$ (3,4,2), $(1, 4, 3)$ (1,4,3);
$(1, 3, 2)$ (1,3,2), $(4, 3, 1)$ (4,3,1), $(1, 4, 3)$ (1,4,3);
$(1, 3, 2)$ (1,3,2), $(4, 3, 1)$ (4,3,1), $(1, 4, 3)$ (1,4,3).

У прикладі перший і другий трикутники, а також третій і четвертий здаються ідентичними, однак, враховуючи, що між цвяхами $#1$ і $#4$ є два дроти одного кольору, трикутники вважаються різними, оскільки для їх утворення використовуються різні дроти.