ferentari

În cartierul Ferentari, $N$ persoane și-au împrumutat bani între ele de-a lungul timpului. Aceste datorii sunt reprezentate sub forma a $M$ tranzacții de tipul: Persoana $X$ trebuie să îi dea persoanei $Y$ suma de $Z$ euro.

Nuțu, „administratorul” cartierului, s-a plictisit de atâtea drumuri făcute între blocuri pentru a colecta banii și vrea să simplifice totul. El știe că dacă Ion îi dă lui Vasile 50€ și Vasile îi dă lui Gheorghe 50€, e mult mai eficient ca Ion să îi dea direct lui Gheorghe acei 50€.

Nuțu vrea să găsească numărul minim de tranzacții directe necesare pentru ca, la final, fiecare persoană să aibă aceeași situație financiară netă (balanță) ca în situația inițială.

Cerință

Cunoscând cele $M$ tranzacții inițiale, determinați numărul minim de transferuri de bani necesare pentru a stinge toate datoriile.

Date de intrare

Fișierul ferentari.in conține pe prima linie numerele $N$ (numărul de persoane) și $M$ (numărul de tranzacții). Următoarele $M$ linii conțin câte trei numere $X, Y, Z$, cu semnificația că persoana $X$ îi datorează persoanei $Y$ suma $Z$.

Date de ieșire

Fișierul ferentari.out va conține un singur număr reprezentând numărul minim de tranzacții.

Restricții și precizări

• $2 \le N \le 20$
• $1 \le M \le 10^5$
• $1 \le Z \le 10^6$
• Sumele finale de plată/încasare nu depășesc $2 \cdot 10^9$
• Persoanele sunt numerotate de la $0$ la $N-1$.

Exemplu

ferentari.in

3 2
0 1 100
1 2 100

ferentari.out

1

Explicatie

În loc de două tranzacții, persoana 0 îi dă direct 100€ persoanei 2