You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最长回路

题目背景

你猜这是个什么题

题目描述

给定一个有 $n$ 个顶点 $m$ 条边的无向简单连通图，每条边有一个长度，保证这个图中存在一条欧拉路径，求这个图里最长的回路长度。

输入格式

第一行两个整数 $n,m$，接下来 $m$ 行每行三个整数 $x_i,y_i,z_i$ 表示一条连接 $x_i,y_i$ ，长度为 $z_i$ 的边。

输出格式

一个整数表示最长回路的长度。

样例 #1

样例输入 #1

5 8
1 2 1
1 3 1
1 4 1
1 5 1
2 3 1
3 4 1
2 5 1
3 5 1

样例输出 #1

7

样例 #2

样例输入 #2

6 8
1 2 1
1 3 2
1 4 3
2 5 4
3 5 5
4 5 6
5 6 7
6 6 8

样例输出 #2

24

提示

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分，共 $100$ 分。