SPOJ in Gyumri

   Задан ориентированный граф из N вершин и M ребер. Каждое ребро описывается тремя числами X Y Z, где X, Y – номера вершин, которые соединяет ребро, а Z – вес ребра, который может быть отрицательным. Необходимо определить количество пар вершин X Y (X <> Y), минимальное расстояние между которыми невозможно найти, т.е. из-за отрицательных ребер минимальный путь между ними можно бесконечно уменьшать.

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

   N M

   X[1] Y[1] Z[1]

   X[2] Y[2] Z[2]

   …

   X[M] Y[M] Z[M]

Где:

   N – количество вершин (1 ≤ N ≤ 250).

   M – количество ребер (1 ≤ M ≤ 1000).

   X[i] Y[i] Z[i] - описание ребра из вершины X[i] в вершину Y[i] с весом Z[i] (-100 ≤ Z[i] ≤ 100).

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

   Ans – количество пар вершин, минимальное расстояние между которыми невозможно найти.

Пример.