Minimum Route for Visiting Relatives in Chongqing

Chongqing city has \(n\) stations and \(m\) bidirectional roads connecting them. Each pair of stations is connected by at most one road, and the network is connected: from any station you can reach any other station via one or more roads. The travel time of a path is the sum of the travel times of all the roads on that path.

Jiajia lives at station 1 and has five relatives living at stations \(a, b, c, d, e\) (given in arbitrary order). With the upcoming New Year, Jiajia wants to deliver holiday greetings by visiting every relative exactly once, starting from his home at station 1. Find the minimum total travel time required for him to complete his visits.

Note: Jiajia does not need to return to station 1 after visiting all relatives.

This problem can be solved by first computing the shortest path between all pairs of the 6 relevant stations (station 1 and the five given stations) (using algorithms like Dijkstra or Floyd–Warshall), and then solving a Traveling Salesman Problem (TSP) on these 6 nodes using dynamic programming with bitmasking.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of stations and the number of roads.

The next \(m\) lines each contain three integers \(u, v, t\), indicating that there is a bidirectional road between station \(u\) and station \(v\) that takes \(t\) time to travel.

The last line contains 5 distinct integers \(a, b, c, d, e\) — the stations where Jiajia's relatives live.

outputFormat

Output a single integer, which is the minimum total travel time required for Jiajia to visit all five relatives starting from station 1.

sample

6 7
1 2 2
1 3 5
2 3 2
2 4 3
3 5 3
4 6 2
5 6 1
2 3 4 5 6

10