410317: GYM104009 A Accountancy

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.

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.

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

3 4
1 2 10
2 1 5
2 3 10
1 3 10

2

4 3
1 2 15
1 3 15
1 4 15

3

3 3
1 2 10
2 3 10
3 1 10

0

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.