题目描述

小坤要在附近的景区游玩一天。景区共有 $n$ 个景点，景点之间由 $m$ 条双向观景道连接。

小坤可以让妈妈开车把他送到任意景点开始游玩，也可以在任意景点结束。为了防止故意拖延，妈妈不允许他到达同一个景点两次。小坤希望在遵守这一限制的前提下，选择总长度尽可能长的游玩路线。

请计算他能够走过的最长路程。路线可以只包含一个景点，此时长度为 $0$。

输入格式

第一行输入两个正整数 $n,m$。接下来 $m$ 行，每行三个整数 $a,b,c$，表示景点 $a,b$ 之间有一条长度为 $c$ 的双向观景道。

输出格式

输出一个整数，表示不重复经过景点时能够得到的最长路线长度。

数据范围与约定

$1\le n\le20$，$0\le m\le50$；任意两个景点之间至多有一条道路，答案在 int 范围内。

可见测试数据

输入数据 1

1 0

输出数据 1

0

输入数据 2

2 0

输出数据 2

0

输入数据 3

4 4
1 2 23
3 4 39
2 3 41
2 4 7

输出数据 3

103