4224: 西樵山旅行(tour)（NHOI2019PJ模拟）

题目描述:

周末桐桐和家人到西樵山行山，西樵山上有n个观景点，所有观景点之间共有行人道共m条。为了安全，那些没有行人道的观景点桐桐是不敢去的，但她也不喜欢去同一个观景点两次或以上，假设桐桐一家人开始可以在任一观景点开始行山，也可以在任一观景点结束她们的活动，问桐桐最多可以走多长的路？ 
输入格式： 
第一行，两个用空格隔开的整数n、m. 
之后m行，为每条行人道的信息：两端观景点编号、长度。 
输出格式： 
一个整数，表示她们最长步行的路程。 
输入样例： 
4 6 
1 2 10 
2 3 20 
3 4 30 
4 1 40 
1 3 50 
2 4 60 
输出样例： 
150 
数据范围：
对于100%的数据:n≤20，m≤50，保证观景点两两之间不会有多条行人道连接。