Problem Description

Young Punch is trying to visit all $ N $ candy shops.

At some of these shops, he can get a stamp on his card. With the stamp from a shop, he can get bonus candies at some other shops.

However, Punch does not want to visit the same shop twice. Therefore, for example,

• With the stamp from shop $ A $, he can get 3 candies at shop $ B $
• With the stamp from shop $ B $, he can get 2 candies at shop $ A $

If these two conditions overlap, he has to give up one of the candies. In this case, it is better to give up the latter and get the 3 candies from the former.

What is the maximum number of candies Punch can get?

Input Format

The input is given from the standard input in the following format:

$ N $ $ E $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ : $ a_E $ $ b_E $ $ c_E $

• The first line contains the number of candy shops $N\ (1\ ≦\ N\ ≦\ 16)$ and the number of shop relationships for getting candies $E\ (0\ ≦\ E\ ≦\ N×N)$ separated by a space.
• The next $ E $ lines contain information about the shop relationships for getting candies.
  The $ i $-th line contains three integers $a_i\ (1\ ≦\ a_i\ ≦\ N)$, $b_i\ (1\ ≦\ b_i\ ≦\ N)$, $c_i\ (1\ ≦\ c_i\ ≦\ 1000)$.
  These represent that "with the stamp from shop $ a_i $, he can get $ c_i $ candies at shop $ b_i $".
• It is guaranteed that when $ i≠j $, $ a_i≠a_j $ or $ b_i≠b_j $.

Output Format

Output the maximum number of candies Punch can get in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

2 2
1 2 3
2 1 2

Sample Output #1

3

Sample Input #2

4 3
1 2 10
1 3 20
1 4 30

Sample Output #2

60

Sample Input #3

3 3
1 2 20
2 3 30
3 1 10

Sample Output #3

50

Sample Input #4

16 1
4 4 1000

Sample Output #4

0

Sample Input #5

4 6
4 1 3
1 3 3
4 2 3
3 4 2
2 3 3
2 2 10

Sample Output #5

12

Notes/Hints

Partial Points

If you solve the test cases where $1\ ≦\ N\ ≦\ 8$, you will be awarded 130 points as partial credit.

Sample Explanation 1

This is the example mentioned in the problem statement.

Sample Explanation 2

He can get all the candies.

Sample Explanation 3

By giving up 10 candies, he can achieve the maximum.

Sample Explanation 4

Since he cannot visit the same shop twice, he cannot get any candies. Also, there may be some shops that are not related to this stamp service.

见题面 Input 部分

见题面 Output 部分