题目描述

一个地区有 $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

输入 #1

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

输出 #1

1110

输入输出样例 #2

输入 #2

10 1
5 9 1

输出 #2

1

输入输出样例 #3

输入 #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

输出 #3

20

说明/提示

样例 1 解释

如果按 $4→1→3→2$ 的顺序旅行，你经过的道路总长度为 1110。

样例 2 解释

可能存在没有与任何道路相连的城镇。

样例 3 解释

数据范围

• $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$
• 所有输入值都是整数。