Fişierul intrare/ieşire:	zeroc.in, zeroc.out	Sursă	Lot Cluj 2009, Baraj 6
Autor	Mugurel Ionut Andreica	Adăugată de	Sima Cotizo •sima_cotizo
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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 (1 ≤ i ≤ M) 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), ..., mu(q), astfel încât b_mu(i) = a_mu(i+1) (1 ≤ i ≤ 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

• 1 ≤ N ≤ 2000
• 0 ≤ M ≤ 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

Explicaţie

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

Cum se trimit solutii?