# 覆盖所有道路的巡检

时间限制：1.5 秒；内存限制：256 MiB。时限按目标环境标准程序最慢中位数乘2，向上取整至0.5秒；见[评测环境](../../../docs/评测环境与性能.md)。

## 背景故事

道路测绘员要沿每一条道路至少走一次，完成记录后回到出发点。道路可以重复经过，出发点也可以自由选择。请规划总路程最短的一次巡检。

(本故事由GPT-6重写)

## 形式化问题描述

给定一个连通无向带权多重图，有 $n$ 个顶点和 $m$ 条边。允许两个不同顶点之间有多条边，不允许自环。每条输入边都是独立的道路，重边必须分别覆盖。

选择一个起点，沿边行走，使每条边至少经过一次，最后回到起点。可以重复经过边，费用是所有经过边的权值之和。求最小费用，以及能达到最小费用的最小编号起点。顶点的度数按边的条数计算，重边分别计数。

## 输入格式

第一行 `n m` .接下来 $m$ 行，每行 `u v w` ，表示端点为 $u,v$ 、权值为 $w$ 的无向边。

## 输出格式

输出两行。第一行为满足要求的最小编号起点，第二行为最小费用。不需要输出具体路线。

## 样例 1

### 输入

```text
3 3
1 2 1
2 3 2
3 1 3
```

### 输出

```text
1
6
```

## 样例 2

### 输入

```text
3 2
1 2 4
2 3 5
```

### 输出

```text
1
18
```

## 样例 3

### 输入

```text
4 5
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
```

### 输出

```text
1
10
```

## 样例 4

### 输入

```text
5 5
1 2 2
2 3 3
2 4 7
2 5 5
3 4 2
```

### 输出

```text
1
26
```

## 样例解释

样例1的三条边形成欧拉回路，费用为6。样例2是一棵树，每条边都必须往返，总费用为18。样例3只需多走一次权值为1的边，总费用为10。样例4的最小费用为26。

![示意图](assets/example.svg)

样例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,\ |\{v:\deg(v)\equiv1\pmod2\}|\le20$ |

共10个测试点，每点占10%；完整配方见[测试说明](tests/README.md)。