INGRED  Ingredients
You are given n cities with m bidirectional roads connecting them and the length of each road. There are two friends living in different cities who wish to collect some ingredients available at different stores to make cake. There are s such stores. They need not come back home after purchasing the ingredients. Petrol is expensive and they would hence like to travel minimum total distance (sum of distance distance travelled by both kids). Help them find out what this distance is.
Input
n m
(m lines of the form a_{i} b_{i} c_{i})
Here n is number of cities, m is number of roads, a_{i} and b_{i} are the cities (0 indexed) the roads connect and c_{i} is the length of this road
s where s is the number of stores
(1 line containing s space separated integers indicating the city number in which the stores are located.)
(two space separated integers indicating the cities in which the two kids live)
Output
Single integer x where x is the minimum distance that the duo will travel that is minimum sum of distance travelled by first kid and second kid.
Constraints:
2 ≤ n ≤ 100
1 ≤ m ≤ (n * (n  1)) / 2
0 ≤ a, b < n
0 ≤ c ≤ 1000
1 ≤ s ≤ 8
Sample
Input: 5 6 0 1 5 1 4 1 0 4 10 0 2 2 1 2 3 2 3 4 2 2 4 0 1 Output: 3
Problem Setter: Vidit Gupta
hide comments
nobel_ruet:
20180603 02:31:55
Is the graph is connected . IF both boys can't go to a store than what will be the answer? Last edit: 20180603 02:32:19 

mahmud2690:
20170219 19:30:20
all of the s stores must be visited or not? 

~!(*(@*!@^&:
20160827 06:40:48
Should be clear that each boy has to buy exactly s items; or both of them will buy s items? Last edit: 20160827 06:41:09 

Shubhojeet Chakraborty:
20160601 20:59:47
lesson learnt..sort the array before using next_permutation.


ISHANI:
20140929 15:09:11
Really Awesome Problem.


785227:
20140615 19:16:48
Awesome problem. Enjoyed solving it :) 

praveen123:
20140208 09:13:09
Increase the font size please 
Added by:  darkshadows 
Date:  20140128 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 