This problem can be solved with bit DP (Dynamic Programming) in a total of \(O((N+M)^2 2^{N+M})\) time.

More basic related problem: ABC180E “Traveling Salesman among Aerial Cities”

If \(M=0\), the problem can be solved by the following DP:

\(DP[i][S]=\) minimum duration required when you are currently at town \(i\) and the set of towns you visited is \(S\);

\(DP[i][S]=\min\{DP[j][S\setminus \{i\}]+\mathrm{time}(i,j) \mid j\in S\setminus\{i\}\}\)
where \(\mathrm{time}\) denotes the time required from town \(i\) to town \(j\).

Even if \(M>0\), we can solve it similarly by “assuming treasure boxes as towns and allowing returning to the origin without visiting treasure boxes.” We can determine the number of boosters by \(S\), so we do not have to maintain an additional information.

Sample code (C)
Sample code (Python)

Alternatively, you can “solve the Traveling Salesman Problem (TSP) for each of \(2^M\) fixed sets of treasure boxes to visit,” whose cost is \(O((N+M)^2 2^N3^M)\) time in total. If you are using a sufficiently fast language, you can still fit in the time limit too.