Immediate Delivery

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.

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.

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.