Problem G
Going Dutch

Picture by ben_osteen on Flickr.

You could each take all the receipts showing that someone paid something for you, and then pay that person back. But then you would need a lot of transactions, and you want to keep up the lazy spirit from your trip. In the end, it does not matter who transfers money to whom; as long as in the end, everyone’s balance is $0$.

Can you figure out the least number of transactions needed to settle the score? Assume everyone has enough spare cash to transfer an arbitrary amount of money to another person.

Input

Input consists of:

• A line containing two integers $M$, the number of people in the group, with $1\leq M \leq 20$, and $N$, the number of receipts from the trip, with $0\leq N\leq 1000$.

• $N$ lines, each with three integers $a, b, p$, where $0 \leq a,b < M$, and $1 \leq p \leq 1000$, signifying a receipt showing that person $a$ paid $p$ euros for person $b$.

Output

Output a single line containing a single integer, the least number of transactions necessary to settle all bills.

4 2
0 1 1
2 3 1

2

5 5
0 1 3
1 2 3
2 3 3
3 4 3
4 0 3

0

5 4
0 1 1
0 2 1
0 3 1
0 4 1

4