Description

周末桐桐和家人到西樵山行山，西樵山上有n个观景点，所有观景点之间共有行人道共m条。为了安全，那些没有行人道的观景点桐桐是不敢去的，但她也不喜欢去同一个观景点两次或以上，假设桐桐一家人开始可以在任一观景点开始行山，也可以在任一观景点结束她们的活动，问桐桐最多可以走多长的路？

Input Format

第一行，两个用空格隔开的整数n、m. 之后m行，为每条行人道的信息：两端观景点编号、长度。
对于100%的数据:n≤20，m≤50，保证观景点两两之间不会有多条行人道连接

Output Format

一个整数，表示她们最长步行的路程。

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

150

Source

NHCZ-2019M