Carpool

Time limit1sMemory limit128 MB

Summary

Split n people into the fewest 5-seat cars, route each car through its passengers' errand stops, and minimize the maximum car travel time.

Level: Hard8 of 10
Topics: Graph, Shortest path, Dynamic programming, Bit manipulation
Solved: No attempts yet

Problem

A group of friends has just finished their computer science assignments. The weather is beautiful, so they decide to head to Joe's house for a BBQ. After all that coding they are too tired to walk, but between them they have more than enough cars to drive everyone there.

On the way, each friend needs to run one quick errand: Joe has to stop at the supermarket for burgers and pop, Jenn wants to grab a frisbee from her house, Jim would rather pick up a pizza, Jerry needs his sunglasses, and so on — every person has exactly one errand to make.

The friends want to reach Joe's house as quickly as possible, so they must decide who rides in which car. Help them by computing an assignment of people to cars that minimizes the time until everyone has arrived.

The city is described by roads between landmarks. The places people must visit for their errands are numbered $1$ through $n$ ; the campus, where everyone starts, is numbered $0$ , and Joe's house is numbered $n+1$ . Every car drives at $60$ km/h — that is, one kilometre per minute — so the driving time along any route equals its length in kilometres. A car may pass through any place without stopping; it only stops for the errand of each person it carries, and each such stop takes $5$ minutes.

Each car starts at the campus, visits (in the best possible order) the errand locations of its passengers, and finishes at Joe's house. Its travel time is its total driving time plus $5$ minutes for every passenger. To be kind to the environment, the friends use as few cars as necessary, and each car can carry at most $5$ people.

The overall travel time is the maximum of the travel times of the individual cars. An optimal assignment is one that minimizes this overall travel time.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 15$ , $1 \le m \le 1000$ ): the number of people in the group and the number of roads in the city.

Each of the next $m$ lines describes one stretch of road with three integers $a$ , $b$ , and $\ell$ , where $0 \le a, b \le n+1$ are the two places it connects and $\ell$ is its length in kilometres. Every road may be driven in both directions, and a pair of places may be joined by more than one road. The roads connect every place to every other place, so the graph is connected.

Output

Print a single integer: the minimum possible overall travel time, in minutes — that is, the smallest achievable value of the maximum car travel time, over all assignments that use the fewest cars and put at most $5$ people in each car.

Examples3

Example 1
Input
```
1 2
0 1 15
1 2 10
```
Expected output
```
30
```
Example 2
Input
```
2 3
0 1 10
1 2 10
2 3 10
```
Expected output
```
40
```

Example 3

Input

Expected output