Rabbit Party

Interview

Time limit5sMemory limit512 MB

Summary

Choose a subset of rabbits to maximize the sum over guests of the minimum friendliness toward any other guest; uninvited pairs have friendliness 0.

Level: Medium6 of 10
Topics: Graph, Brute force, Greedy, Implementation
Solved: No attempts yet

Problem

A rabbit named Taro decided to hold a party and invite some friends as guests. He has n rabbit friends, and m pairs of rabbits are also friends with each other. The friendliness of each pair is given as a positive integer. If two rabbits are not friends, their friendliness is taken to be 0.

When a rabbit is invited to the party, his satisfaction score is defined as the minimum friendliness with any other guest. The satisfaction of the party itself is defined as the sum of the satisfaction scores of all the guests.

To maximize the satisfaction score of the party, whom should Taro invite? Write a program to calculate the maximal possible satisfaction score of the party.

Input

The first line of the input contains two integers, n and m (1≤n≤100, 0≤m≤100). The rabbits are numbered from 1 to n.

Each of the following m lines has three integers, u, v and f. u and v (1≤u,v≤n, u≠v) are the rabbits' numbers, and f is their friendliness (1≤f≤1,000,000).

You may assume that the friendliness of a pair of rabbits is given at most once.

Output

Output the maximal possible satisfaction score of the party in a line.

Examples4

Example 1
Input
```
3 3
1 2 3
2 3 1
3 1 2
```
Expected output
```
6
```
Example 2
Input
```
2 1
1 2 5
```
Expected output
```
10
```
Example 3
Input
```
1 0
```
Expected output
```
0
```
Example 4
Input
```
4 5
1 2 4
1 3 3
2 3 7
2 4 5
3 4 6
```
Expected output
```
16
```