规划远足

核心节点被切断了，Zero的网络分裂成了无数孤岛。有些孤岛上还有反抗军的据点——他们被困住了，无法互相通信。

"我们要规划一条路线。"你说，"从起点出发，经过每一座桥，每座桥至少走一次，最后回到起点。"

"这就像……"CC想了想，"像远足。从营地出发，走过每条小路，最后回到营地。"

"对。"

你开始写。每个孤岛是一个节点，每座桥是一条边。要找一条从起点出发、经过每条边至少一次、最后回到起点的最短路径。对于已经连通的块，可以直接走欧拉回路——每条边只走一次。对于不连通的块，需要在块之间添加额外的路径。

屏幕上跳出了结果。额外路径长度：47。

"又是47。"CC说。

"47座额外的桥。"Echo说，"连接47个孤岛。"

"我们建得起？"你问。

"建不起。"Echo说，"但我们可以用已有的桥，多走几次。"

"多走几次？"

"对。"Echo说，"远足的时候，有些路要来回走。不是因为我们想走，是因为那是唯一的路。"

CC看着地图，看着那些发光的孤岛。

"那就走。"她说，"走两遍。"

题目描述

$n$ 个节点，$m$ 条边的无向图。求从1号节点出发，经过每条边至少一次，最后回到1号节点的最短路径长度。

输入格式

$n, m$。然后 $m$ 条边 $(u, v, w)$。

输出格式

最短路径长度。

输入样例

3 2
1 2
2 3

输出样例

1073741824
1073741824
1073741824

提示

• 先找连通块。每个连通块内走欧拉回路。
• 连通块之间需要额外的路径连接。额外路径 = 连通块之间的最小距离。
• 用Tarjan或DFS找连通块。

"路线规划好了。"你说。

"走。"CC说。

"走。"Echo说。

你们走上了那条路。有些桥只走一次，有些桥走了两次。但无论如何，所有孤岛都被连在了一起。

"下一题。"Echo说，"是银河。"

"银河？"

"对。"Echo说，"最大的图。"

[第七题：丈量银河]