HZNUOJ

今天要跑多远呢

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:115     AC:44     Score:100.00

Description

今今是一个热爱运动的小朋友,她喜欢每天早上打卡跑步,顺便欣赏沿途的风景。她希望每天早上都可以在不重复经过同一个打卡点的情况下跑最远的距离。
今今可以从任意点开始打卡出发,在任意有道路的打卡点之间奔跑,但是她的数学不太好,希望有小朋友能帮她计算一下每天可以跑的距离。
      

Input

第一行,两个用空格隔开的整数打卡点n、道路数目m;之后m行,为用空格分隔的每条道路的两端打卡点以及道路的长度(正整数)。
    

Output

一个整数,表示今今在不经过重复点的情况下可以跑的最长距离。

Samples

input
4 6 1 2 10 2 3 20 3 4 30 4 1 40 1 3 50 2 4 60
output
150

Hint

所有数据n<=15,m<=30,每两个打卡点之间没有重复道路。

注意:测试数据输入的不一定是连通图。

Author

MAO, Yuying