Going Dutch

Time limit2sMemory limit512 MB

Summary

Given each person's net balance from the receipts, find the minimum number of money transfers that settles everyone to zero.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Backtracking, Greedy
Solved: No attempts yet

Problem

You and your friends have just returned from a vacation in the mountains of the Netherlands. Splitting the bill on every expense during the trip is annoying, so you kept all the receipts instead and wrote down who paid how much for whom. Now it is time to settle the bill.

Each of you could take the receipts showing that someone paid something for you and pay that person back. That takes a lot of transactions, and you want to keep up the lazy spirit from the trip. It does not matter who transfers money to whom, as long as everyone's balance is $0$ in the end.

Find the least number of transactions needed to settle the score. One transaction moves money from one person to one other person, and assume everyone has enough spare cash to transfer any amount.

Input

The first line contains two integers $M$ , the number of people in the group, and $N$ , the number of receipts from the trip, with $1 \le M \le 20$ and $0 \le N \le 1000$ .

Each of the next $N$ lines contains three integers $a$ , $b$ , $p$ with $0 \le a, b < M$ and $1 \le p \le 1000$ , a receipt showing that person $a$ paid $p$ euros for person $b$ .

Output

Print a single integer on one line, the least number of transactions necessary to settle all bills.

Examples3

Example 1
Input
```
4 2
0 1 1
2 3 1
```
Expected output
```
2
```
Example 2
Input
```
5 5
0 1 3
1 2 3
2 3 3
3 4 3
4 0 3
```
Expected output
```
0
```
Example 3
Input
```
5 4
0 1 1
0 2 1
0 3 1
0 4 1
```
Expected output
```
4
```