졸업 테이블

면접 대비

시간 제한1초메모리 제한1024 MB

요약

친구가 최대 2명인 사람들이 둘러앉는 원형 식탁에서, 함께 앉혀 줄 친구 쌍을 골라 받을 수 있는 뇌물의 합을 최대로 하는 문제입니다.

난이도: 보통10점 중 5점
유형: 그래프, 그리디
정답자: 아직 제출이 없습니다

문제

컴퓨터공학과 졸업 연회의 좌석 배치를 맡게 되었다. 참석자는 $n$ 명이며 모두 큰 원형 테이블에 둘러앉아야 한다. 참석자 중 일부는 친구이고 서로 옆자리에 앉기를 원한다. 참석자가 모두 컴퓨터공학 전공자라서 친구는 최대 2명이다.

이 친구 쌍들은 비공개로 함께 앉기를 요청하며, 요청을 들어주면 뇌물을 주겠다고 제안했다. 당신은 청렴을 지키고 싶지만 돈도 중요하다. 그래서 해당 쌍의 요청을 들어줄 수 있을 때만 뇌물을 받는다. 받을 뇌물의 조합을 골라 받는 금액의 합이 최대가 되도록 하라.

입력

첫 줄에 두 정수 $N$ ( $1 \leq N \leq 5000$ )과 $M$ ( $0 \leq M \leq N$ )이 주어진다. 각각 참석자 수와 좌석 요청 수다. 이어서 $M$ 개의 줄에 세 정수 $u$ , $v$ ( $1 \leq u < v \leq n$ ), $c$ ( $1 \leq c \leq 10^8$ )가 주어진다. 이는 참석자 $u$ 와 $v$ 가 옆자리에 앉는 대가로 $c$ 달러를 낼 의사가 있다는 뜻이다.

같은 쌍이 두 번 요청하는 일은 없으며, 각 참석자는 최대 두 개의 요청에 등장한다.

출력

모든 가능한 좌석 배치에서 벌 수 있는 금액의 최댓값을 출력한다.

예제2

예제 1
입력
```
3 3
1 2 1
2 3 2
1 3 3
```
예상 출력
```
6
```
예제 2
입력
```
5 4
1 2 1
2 3 2
1 3 3
4 5 4
```
예상 출력
```
9
```