Ambulance Antics

One ambulance has to carry patients who are scattered across the city to the hospital. The ambulance holds at most three patients at a time, and it has to drive back to the hospital to drop patients off. Loading and unloading take no time.

The city consists of intersections and streets. One intersection holds the hospital, and every other intersection holds one waiting patient. Every street is bidirectional, and each street has a driving time in minutes that is the same in both directions. The ambulance starts at the hospital.

The ambulance may pass through any intersection as many times as it likes. Compute the smallest number of minutes needed to bring every patient to the hospital. The ambulance stands at the hospital once the last patient is dropped off.

The first line contains the number of test cases $T$.

The first line of each test case contains two integers $N$ and $M$, the number of intersections holding a patient and the number of streets. Each of the next $M$ lines contains three integers $a_i$, $b_i$, $c_i$, meaning that a bidirectional street connects intersections $a_i$ and $b_i$ and that driving along it takes $c_i$ minutes.

The city has $N + 1$ intersections, numbered 0 to $N$. The hospital is at intersection $N$, and one patient waits at each of the intersections 0 through $N - 1$.

• $0 < T \le 100$
• $1 \le N \le 20$
• $M > 0$
• $0 \le a_i, b_i \le N$
• $0 < c_i \le 100000$
• A route always exists between any two intersections.
• At most one street connects a given pair of intersections.

For each test case, print one line with the minimum number of minutes needed to deliver every patient to the hospital.