zeroc

Se dă un graf orientat cu $N$ noduri (numerotate de la $1$ la $N$) şi $M$ muchii (numerotate de la $1$ la $M$). Fiecare muchie $i$ este orientată de la $a_i$ la $b_i$ şi are un cost $c_i$ (pozitiv, zero sau negativ). Un ciclu este o secvenţă de muchii distincte $mu(1), mu(2), \dots, mu(q)$, astfel încât $b_{mu(i)}=a_{mu(i+1)} (1 \leq i \leq q-1)$ şi $b_{mu(q)}=a_{mu(1)}$. Costul unui ciclu este egal cu suma costurilor muchiilor ce formează ciclul.

Cerinţă

Ştiind că nu există cicluri de cost negativ în graf, determinaţi câte dintre cele $M$ muchii ale grafului fac parte din cel puţin un ciclu de cost zero.

Date de intrare

Pe prima linie a fişierului de intrare zeroc.in se află numerele naturale $N$ şi $M$, separate printr-un spaţiu. Pe a $i$-a linie din următoarele $M$ linii se află câte $3$ numere întregi, $a_i$, $b_i$, şi $c_i$, separate prin câte un spaţiu şi având semnificaţia că există o muchie orientată de la nodul $a_i$ la nodul $b_i$, având costul $c_i$.

Date de ieșire

În fişierul de ieşire zeroc.out veţi afişa un singur număr, reprezentând numărul de muchii ale grafului care fac parte din cel puţin un ciclu de cost zero.

Restricții și precizări

• $1 \leq N \leq 2 \ 000$
• $0 \leq M \leq 15 \ 000$
• Costul unei muchii este un număr întreg între $-10 \ 000$ si $10 \ 000$
• Pot exista mai multe muchii între aceeaşi pereche de noduri, eventual chiar şi orientate în acelaşi sens (şi putând avea costuri diferite)

Exemplu

zeroc.in

6 8
1 2 -2
2 3 6
3 4 -2
4 1 -2
4 5 -7
5 2 7
5 6 3
6 1 8

zeroc.out

4

Explicație

Singurele muchii care aparţin unui ciclu de cost zero sunt primele $4$ muchii din fişier.