Under construction

Still being built. Things may change

Immediate Delivery

Time limit3sMemory limit256 MB

Summary
Given a small weighted graph (n ≤ 18), split all junctions between two drivers starting from node 1 so that the larger of their two walk-covering times from node 1 is minimized.
Level

Hard8 of 10

Topics
Bit manipulation, Dynamic programming, Shortest path, Graph
Solved
No attempts yet

Problem

Mike and John are delivery drivers for Immediate Delivery. One day they are asked to deliver a great many packages all across the city.

The transport network of the city they work in consists of junctions and roads connecting those junctions. Every road is bidirectional, and any two junctions can reach each other (directly or through other junctions).

To deliver all the packages, Mike and John must visit every junction. They want to split this task into two parts so as to minimize the time at which the last delivery is completed.

Both drivers start at time 0 from the office (junction 1) at the same moment, and each moves freely along the roads (a road may be traversed more than once). A driver’s travel time is the sum of the times of the roads they traverse, and the last-delivery time is the larger of the two drivers’ travel times. Assign the junctions so that every junction is visited by at least one of them, and make this last-delivery time as small as possible.

Input

The first line contains the number of junctions n and the number of roads m (1 ≤ n ≤ 18).

Each of the following m lines describes one road. It contains the numbers x and y of the two junctions the road connects (1 ≤ x, y ≤ n) and the time t needed to drive along it (1 ≤ t ≤ 1000). There is at most one road between any two junctions, and no road connects a junction to itself.

The office is located at junction 1.

Output

Print a single integer on one line: the earliest time at which the last package can be delivered, that is, the minimum possible last-delivery time.

Examples3

  1. Example 1

    Input
    6 6
1 2 10
2 3 10
3 4 5
4 5 10
5 6 20
2 5 10
    Expected output
    40

  2. Example 2

    Input
    1 0
    Expected output
    0

  3. Example 3

    Input
    2 1
1 2 5
    Expected output
    5