A. Accountancy
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

In Romania, a very popular location for a nice relaxing holiday is Vama Veche. This is a problem about a group of friends and their vacation here.

Because the friends were very relaxed, they were not able to make the calculations needed for splitting the bills. Thus, most of the time they decided to have someone pay and worry about it later. Now they owe money to each other and need to make some bank transfers in order to satisfy everyone. The only problem is that they are lazy and want to make the minimum amount of transactions in order to achieve this.

Formally, you have $$$N$$$ friends and $$$M$$$ conditions of $$$friend_x$$$ owes $$$friend_y$$$ an amount of money equal to $$$val$$$. You need to find the minimum amount of transactions needed so that each friend has no debt and no further money to receive.

Input

The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 20$$$) and $$$M$$$ ($$$0 \leq M \leq N*(N-1)$$$), denoting the number of friends and the number of conditions.

Each of the following $$$M$$$ lines contains $$$3$$$ positive integers: $$$friend_x$$$, $$$friend_y$$$ and $$$val$$$ ($$$1 \leq friend_x, friend_y \leq N$$$, $$$friend_x \neq friend_y$$$, $$$1 \leq val \leq 10^5$$$), denoting that $$$friend_x$$$ owes $$$friend_y$$$ an amount of money equal to $$$val$$$. Each ordered pair of $$$(friend_x, friend_y)$$$ will appear at most once in the input.

Output

On a single line, print the minimum number of transactions needed in order to satisfy all the friends.

Examples
Input
3 4
1 2 10
2 1 5
2 3 10
1 3 10
Output
2
Input
4 3
1 2 15
1 3 15
1 4 15
Output
3
Input
3 3
1 2 10
2 3 10
3 1 10
Output
0
Note

In the first example, the minimum amount of transactions needed is $$$2$$$: $$$friend_1$$$ gives $$$friend_2$$$ $$$15$$$ dollars and $$$friend_2$$$ gives $$$friend_3$$$ $$$20$$$ dollars.

In the second example, the minimum amount of transactions needed is $$$3$$$: $$$friend_1$$$ gives $$$friend_2$$$ $$$15$$$ dollars, $$$friend_1$$$ gives $$$friend_3$$$ $$$15$$$ dollars and $$$friend_1$$$ gives $$$friend_3$$$ $$$15$$$ dollars.

In the third example, no transactions are needed.