The snowplough

graph shortest path dynamic programming bit tricks maps and navigation logistics contests

Snow fell in the night. A snowplough leaves its depot crossing, has to drive along every street of its district at least once and come back. Driving along a street already cleared is an empty run. What is the shortest distance it has to drive?

The streets are two-way, there can be several streets between two crossings, and any street can be driven any number of times. Which crossing the plough leaves from does not affect the answer: the route is closed. Tests five to seven are blocks of central Almaty from the article: squares around Republic Square, the Opera and Ballet Theatre and the Green Bazaar, with street lengths in metres.

Input

The first line holds n and m (2 ≤ n ≤ 5000, 1 ≤ m ≤ 10,000), the number of crossings and streets. Then m lines a b w: a street w metres long between crossings a and b (a ≠ b, 1 ≤ w ≤ 10,000). Every crossing can be reached from every other along the streets. There are at most 22 crossings where an odd number of streets meet.

Output

One number: the length of the shortest closed route that goes along every street at least once.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 6000 ms
Time · Go: 2000 ms
Memory: 256 MB
Judging: 9 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

If every crossing has an even number of streets, the answer is just the sum of the lengths: there is an Eulerian circuit. What gets in the way when there are odd crossings?

2Hint 2

Look at the streets the route drives a second (third…) time. An odd crossing has an odd number of such passes, an even one an even number. What do these extra passes split into?

3Hint 3

In the second sample the odd crossings are 1, 2, 4 and 6. The closest pair is 1 and 2, only 2 metres. What is then left for 4 and 6?

4The idea

The extra passes split into paths between odd crossings, one path per pair, and perhaps cycles, which do not shorten the route. So the answer is the sum of the lengths of all streets plus the smallest sum of shortest distances over a pairing of the odd crossings. And such a route exists: if the shortest paths of the best pairing are duplicated, all degrees become even, and an Eulerian circuit goes along every street (the proof is in the article). The distances between odd crossings come from Dijkstra from each of them, and the best pairing from bitmask DP.

5Walkthrough

rest(mask) is the smallest sum for the crossings not in the mask; the lowest free crossing i is paired first, with each free j: rest(mask) = min(dist[i][j] + rest(mask ∪ {i, j})). The rule “lowest first” loses no pairings, since i is paired with someone anyway, but does not go through one pairing in different orders either. There are 2²² masks, but under this rule fewer than thirty thousand occur, so recursion with memoisation in a dictionary is handy.

In the second sample the sum of the streets is 41. The greedy choice takes the pair 1–2 for 2 metres, and 17 is left for 4 and 6: 19 in all. The pairs 1–6 (6 metres) and 2–4 (9) are better: 15, answer 56. In the square around Republic Square (the fifth test) greed loses 250 metres out of 1690.

5+Solution

6Complexity

Dijkstra from each of the k ≤ 22 odd crossings is O(k · m log n), the pairing is the number of masks met times k. The route itself need not be built: its length is enough.

7Common mistakes

Greedy pairs. “Nearest first” loses already in the second sample: the last crossings are left far from each other.
Straight-line distance, or a single street. The second pass goes along streets, and the path between a pair is the shortest path in the graph, not an edge between them.
Going through all masks in a row. A loop over 2²² masks trying pairs in each is hundreds of millions of steps in Python; the rule “lowest first” and memoisation keep only the needed states.

Algorithms behind it

GRA Algorithm Eulerian path Go along every edge exactly once: the odd-vertex rule and Hierholzer's algorithm in O(E). O(V + E) 3 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems