zmeu

The Dragon has locked up the Emperor's 5 daughters in his castle. Prince Charming has come to get them out of the castle, using the map the Good Fairy gave him. The map contains the castle's n rooms, numbered from 1 to n and the m tunnels between rooms. Also marked are the rooms where the girls and Prince Charming are, the time needed to cross each tunnel and the p rooms through which they can exit the castle.

Task

Determine the minimum amount of time needed by Prince Charming to get to the 5 girls and get them out of the castle.

Input data

The first line of input file zmeu.in contains 3 numbers n, m and p, representing the number of rooms, number of tunnels and, respectively, the number of castle exits.
The second line contains the numbers of 6 different rooms: the first number is the room in which Prince Charming is in, and the other five the rooms where the girls are.
The following m lines contain 3 numbers each, representing the m tunnels: the first two represent the rooms the tunnel connects and the third the time needed to cross the tunnel.
The last p lines contain a number each, representing the rooms through which one can exit the castle. All numbers are positive integers, and numbers located on the same line are separated by a space.

Output data

The first line of file zmeu.out will contain a single line with a single number, the minimum time needed to start from Prince Charming's room, going through the rooms of the 5 girls and getting to a room that connects to the outside. Only time needed to cross tunnels will be taken into consideration; the amount of time required to cross rooms or exit the castle will be ignored. 

Constraints

Example

zmeu.in

zmeu.out

 Explanation

10 11 3
2 1 7 5 10 6
1 7 3
1 2 2
1 3 4
2 3 2
2 8 1
2 4 3
3 4 2
3 5 2
3 6 5
6 10 3
6 9 4
7
4
8

29

 A possible route is:
2-1-7-1-2-3-5-3-6-10-6-3-4

Time limit: 1 second/test

prof. Nistor Mot
Braila "N.Balcescu" National High School
Contact:emotz_ro@yahoo.co.uk