E - 除雪車の巡回 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は市の除雪作業の計画を担当しています。市内には N 個の交差点があり、交差点には 1 から N までの番号が付けられています。交差点間は M 本の道路で結ばれており、各道路は双方向に通行可能です。同じ頂点対を結ぶ道路が複数存在することもありますが、それらは異なる道路として区別されます。 i 番目の道路は交差点 U_i と交差点 V_i を結んでおり、除雪車がどちらの方向に通過する場合も W_i 分かかります。

高橋君は除雪車を交差点 1 にある車庫から出発させ、 M 本の道路のすべてをそれぞれ少なくとも 1 回ずつ通り、最終的に交差点 1 の車庫に戻るルートを計画しなければなりません。各道路はいずれか一方の方向に 1 回通過すれば除雪されたものとみなし、両方向それぞれで通過する必要はありません。また、除雪車は同じ道路を同じ方向・異なる方向を問わず 2 回以上通ることもできます。途中で交差点 1 を何度経由しても構いません。燃料には限りがあるため、できるだけ短い時間で巡回を完了させたいと考えています。

除雪車が交差点 1 を出発し、すべての道路をそれぞれ少なくとも 1 回ずつ通り、交差点 1 に戻ってくるために必要な最小の合計移動時間（分）を求めてください。

なお、与えられるグラフは連結であることが保証されます。

制約

  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • グラフは連結である
  • 奇数次数の頂点の個数は 16 以下である。ここで頂点の次数とは、その頂点に接続する辺の本数であり、多重辺がある場合も各辺を 1 本ずつ別々に数える
  • 同じ頂点対を結ぶ道路が複数存在することがある（多重辺が存在しうる）
  • 入力はすべて整数である

入力

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、交差点の数を表す N と道路の数を表す M が、スペース区切りで与えられる。
  • 2 行目から M 行では、各道路の情報が与えられる。
  • 1 + i 行目では、 i 番目の道路が結ぶ 2 つの交差点 U_i , V_i と、通過にかかる時間 W_i （分）が、スペース区切りで与えられる。

出力

除雪車がすべての道路をそれぞれ少なくとも 1 回ずつ通り、交差点 1 に戻るために必要な最小の合計移動時間を、整数で 1 行に出力せよ。

入力例 1

3 3
1 2 4
2 3 5
3 1 6

出力例 1

15

入力例 2

3 2
1 2 3
2 3 5

出力例 2

16

入力例 3

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

出力例 3

48

入力例 4

15 20
1 2 10
2 3 8
3 4 7
4 5 12
5 6 3
6 7 9
7 8 5
8 9 11
9 10 6
10 11 4
11 12 8
12 13 7
13 14 13
14 15 2
15 1 14
1 8 20
3 10 15
5 12 6
7 14 9
2 9 18

出力例 4

228

入力例 5

2 1
1 2 1000000

出力例 5

2000000

Score : 466 pts

Problem Statement

Takahashi is in charge of planning the city's snow removal operations. The city has N intersections, numbered from 1 to N. The intersections are connected by M roads, each of which is passable in both directions. There may be multiple roads connecting the same pair of vertices, but they are treated as distinct roads. The i-th road connects intersection U_i and intersection V_i, and it takes W_i minutes for the snow plow to traverse it in either direction.

Takahashi must plan a route for the snow plow that starts from the depot at intersection 1, traverses each of the M roads at least once, and finally returns to the depot at intersection 1. A road is considered cleared of snow once it is traversed in either one direction; it is not necessary to traverse it in both directions. The snow plow may traverse the same road more than once, regardless of whether it is in the same or opposite direction. It is also allowed to pass through intersection 1 any number of times during the route. Since fuel is limited, Takahashi wants to complete the patrol in as short a time as possible.

Find the minimum total travel time (in minutes) required for the snow plow to depart from intersection 1, traverse every road at least once, and return to intersection 1.

It is guaranteed that the given graph is connected.

Constraints

  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq 10^5
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 1 \leq W_i \leq 10^6
  • The graph is connected
  • The number of vertices with odd degree is at most 16. Here, the degree of a vertex is the number of edges incident to it, where each edge of a multi-edge is counted separately
  • There may be multiple roads connecting the same pair of vertices (multi-edges may exist)
  • All input values are integers

Input

N M
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains N, the number of intersections, and M, the number of roads, separated by a space.
  • The following M lines provide information about each road.
  • The (1 + i)-th line contains the two intersections U_i, V_i connected by the i-th road, and the time W_i (in minutes) required to traverse it, separated by spaces.

Output

Output in a single line the minimum total travel time, as an integer, required for the snow plow to traverse every road at least once and return to intersection 1.

Sample Input 1

3 3
1 2 4
2 3 5
3 1 6

Sample Output 1

15

Sample Input 2

3 2
1 2 3
2 3 5

Sample Output 2

16

Sample Input 3

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

Sample Output 3

48

Sample Input 4

15 20
1 2 10
2 3 8
3 4 7
4 5 12
5 6 3
6 7 9
7 8 5
8 9 11
9 10 6
10 11 4
11 12 8
12 13 7
13 14 13
14 15 2
15 1 14
1 8 20
3 10 15
5 12 6
7 14 9
2 9 18

Sample Output 4

228

Sample Input 5

2 1
1 2 1000000

Sample Output 5

2000000