题目描述

在某地有 $N$ 个编号为 $1$ 到 $N$ 的城市，以及 $M$ 条编号为 $1$ 到 $M$ 的道路。

第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，是双向的，道路长度为 $C_i$。

你可以从任意一个城市出发，每经过一个城市后不能再次经过同一个城市。请你求出在满足上述条件下，经过的道路长度之和的最大可能值。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$A_1$ $B_1$ $C_1$
$\vdots$
$A_M$ $B_M$ $C_M$

输出格式

请输出答案。

样例 1

输入

4 4
1 2 1
2 3 10
1 3 100
1 4 1000

输出

1110

样例 2

输入

10 1
5 9 1

输出

1

样例 3

输入

10 13
1 2 1
1 10 1
2 3 1
3 4 4
4 7 2
4 8 1
5 8 1
5 9 3
6 8 1
6 9 5
7 8 1
7 9 4
9 10 3

输出

20

说明/提示

限制条件

• $2 \leq N \leq 10$
• $1 \leq M \leq \frac{N(N-1)}{2}$
• $1 \leq A_i < B_i \leq N$
• $(A_i, B_i)$ 互不相同
• $1 \leq C_i \leq 10^8$
• 所有输入均为整数

样例解释 1

如果按照 $4 \to 1 \to 3 \to 2$ 的顺序移动，经过的道路长度之和为 $1110$。

样例解释 2

可能存在没有道路连接的城市。

样例解释 3

由 ChatGPT 4.1 翻译