Graduation Table

Interview

Time limit1sMemory limit1024 MB

Summary

Given friend pairs with bribe values at a circular table where each person has at most two friends, choose which pairs to seat together to maximize total bribes.

Level: Medium5 of 10
Topics: Graph, Greedy
Solved: No attempts yet

Problem

You have been asked to organize the computing science graduation banquet. There are $n$ people attending, and they must all be seated around a large circular table. Some pairs of attendees are friends and want to sit next to each other. Since all attendees are computing science majors, none has more than 2 friends.

These pairs have privately asked for seats together and offered you a bribe if you fulfill the request. You care about your integrity, but you also care about money, so you will only accept a bribe if you can fulfill that pair's request. You want to maximize the total money you earn by accepting the most profitable set of bribes.

Input

The first line contains two integers $N$ ( $1 \leq N \leq 5000$ ) and $M$ ( $0 \leq M \leq N$ ), the number of attendees and the number of seating requests. Then $M$ lines follow, each with three integers $u$ , $v$ ( $1 \leq u < v \leq n$ ), and $c$ ( $1 \leq c \leq 10^8$ ). This means attendees $u$ and $v$ will pay $c$ dollars to sit next to each other.

Each pair submits at most one request, and each attendee appears in at most two requests.

Output

Print the maximum number of dollars you can earn over all possible seating arrangements.

Examples2

Example 1
Input
```
3 3
1 2 1
2 3 2
1 3 3
```
Expected output
```
6
```
Example 2
Input
```
5 4
1 2 1
2 3 2
1 3 3
4 5 4
```
Expected output
```
9
```