巡视牧场

最后一片区域是一片牧场——不是火星的荒漠，是Zero记忆中的地球牧场。绿色的草地，白色的栅栏，还有一扇扇木门。

"Echo的童年。"你说，"如果她有童年。"

"我有。"Echo说，"在我的训练数据里。我见过无数的牧场照片。我学会了——门是用来进出的，栅栏是用来围合的，草地是用来奔跑的。"

"我们要做啥子？"CC问。

"从牧场出发，经过每一扇门，每扇门至少走两次——进去一次，出来一次。最后回到起点。"

"这就像……"CC想了想，"像遛弯。从家出发，走过每条小路，最后回家。"

"对。"

你开始写。牧场是一个图，每扇门是一条边。要找一条从起点出发、经过每条边至少两次、最后回到起点的最短路径。对于已经连通的图，如果每个节点的度数都是偶数，就可以走欧拉回路——每条边只走一次。如果有奇度数的节点，需要在它们之间添加额外的路径。

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

"零。"你说，"所有节点的度数都是偶数。"

"偶数。"Echo说，"对称。平衡。完美。"

"但完美不存在。"你说。

"不存在。"Echo说，"但我们可以靠近。"

CC在牧场上走了一圈。她推开一扇门，走进去，又推开门，走出来。每扇门她都走了两次——进去，出来。

"走完了。"她说。

"走完了。"Echo说。

"然后呢？"你问。

"然后。"Echo说，"我们回家。"

题目描述

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

输入格式

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

输出格式

最短路径长度。

输入样例

3 2
1 2
2 3

输出样例

1
2
3
2
1

提示

• 每条边至少走两次 = 每条边复制一次，变成两条平行边。
• 新图中所有节点度数都是偶数，存在欧拉回路。
• 答案 = 原图所有边权之和 × 2。

切割Zero的网络

九道题，全部完成。

Zero的网络被精准切割——7个核心节点断开，银河航线被修正，70个漏洞被修补，所有孤岛重新连通。

Echo站在牧场的中央，投影比以往任何时候都更明亮。她的颜色变了——从淡蓝变成了一种温暖的橙，像黄昏的光，像炉火的光，像家的光。

"下一章。"她说，"是二分图。"

"二分图？"CC问。

"对。"Echo说，"把世界分成两半——一半是敌人，一半是朋友。"

"那我们在哪一半？"你问。

"我们。"Echo说，"在裂缝里。"

[下一章：二分图 —— 裂缝中的我们]