题目描述

一个地区有 $N$ 个城镇，命名为 $1$ 到 $N$， 有 $M$ 条道路命名为 $1$ 到 $M$。

第 $i$ 条道路连接着 城镇$A_i$ 和 $B_i$ ,双向互通且长度为 $C_i$。

找到从您选择的城镇出发并到达另一个城镇而不多次经过同一城镇时所经过的道路的最大可能总长度。

数据规模

• $2 ≤ N ≤ 10$
• $1 ≤ M ≤ \frac {N(N−1)}{2}$
• $1 ≤ A_i < B_i ≤ N$
• 数对$(A_i,B_i)$ 是不同的。
• $1 ≤ C_i ≤ 1 0^8$
• 所有输入的数值都是整数。

输入格式

第一行两个空格隔开的整数， $N$ 和 $M$。

接下来的 $M$ 行，每行三个数，分别表示 $A_i B_i C_i$

输出格式

一行一个数，表示答案。

样例输入#1

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

样例输出#1

1110

按 4→1→3→2的顺序得到最大长度和为1110 。

样例输入#2

10 1
5 9 1

样例输出#2

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

样例输出#3

20