覆盖所有道路的巡检¶
时间限制：1.5 秒；内存限制：256 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见评测环境。
背景故事¶
道路测绘员要沿每一条道路至少走一次，完成记录后回到出发点。道路可以重复经过，出发点也可以自由选择。请规划总路程最短的一次巡检。
(本故事由GPT-6重写)
形式化问题描述¶
给定一个连通无向带权多重图，有 \(n\) 个顶点和 \(m\) 条边。允许两个不同顶点之间有多条边，不允许自环。每条输入边都是独立的道路，重边必须分别覆盖。
选择一个起点，沿边行走，使每条边至少经过一次，最后回到起点。可以重复经过边，费用是所有经过边的权值之和。求最小费用，以及能达到最小费用的最小编号起点。顶点的度数按边的条数计算，重边分别计数。
输入格式¶
第一行 n m .接下来 \(m\) 行，每行 u v w ，表示端点为 \(u,v\) 、权值为 \(w\) 的无向边。
输出格式¶
输出两行。第一行为满足要求的最小编号起点，第二行为最小费用。不需要输出具体路线。
样例 1¶
输入¶
3 3
1 2 1
2 3 2
3 1 3
输出¶
1
6
样例 2¶
输入¶
3 2
1 2 4
2 3 5
输出¶
1
18
样例 3¶
输入¶
4 5
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
输出¶
1
10
样例 4¶
输入¶
5 5
1 2 2
2 3 3
2 4 7
2 5 5
3 4 2
输出¶
1
26
样例解释¶
样例1的三条边形成欧拉回路，费用为6。样例2是一棵树，每条边都必须往返，总费用为18。样例3只需多走一次权值为1的边，总费用为10。样例4的最小费用为26。
样例3：顶点1和3为奇度，多经过一次对角线即可使所有度数变为偶数。
数据范围与分值¶
\(2\le n\le10^5\) ，\(n-1\le m\le2\cdot10^5\) ，\(1\le u,v\le n\) ，\(u\ne v\) ，\(0\le w\le1000\) .图连通。非树输入至多有20个奇度顶点；树输入没有奇度顶点数量限制。
| 分值 | 额外限制 |
|---|---|
| 20% | \(m=n-1\) |
| 30% | \(m\ge n,\ \deg(v)\equiv0\pmod2\) |
| 50% | $m\ge n,\ |
共10个测试点，每点占10%；完整配方见测试说明。