Explorace

An explorace is held to welcome new students. Each team must visit every checkpoint in any order it chooses, completing a designated activity at each checkpoint.

To keep newcomers from wandering off, the organizers place staff members on some paths and allow students to use only staffed paths. Staff are limited, so the organizers want to minimize the total length of the staffed paths while still guaranteeing that every pair of checkpoints is connected by some route. Each path connects checkpoints $a$ and $b$ in both directions with length $d$, and every path length is at most $500$. For each test case, find the minimum possible total length of the paths that must be staffed.

The first line gives the number of test cases $T$ ($1 \le T \le 10$). The first line of each test case gives the number of checkpoints $N$ and the number of candidate paths $M$ ($1 \le N \le 20$, $1 \le M \le N(N-1)$). Each of the following $M$ lines gives three integers $a$, $b$ and $d$ ($1 \le a, b \le N$, $1 \le d \le 500$), meaning there is a path of length $d$ connecting checkpoint $a$ and checkpoint $b$.

For each test case, print one line in the form Case #x: y meters, where $x$ is the 1-based test case number and $y$ is the minimum total length of the paths to staff.