Barr the bear is in BIG trouble! He has angered a swarm of bees by stealing their honey, and they are out to get him! Help Barr get away in time while at the same time fulfilling some of his unreasonable requirements.
Barr is in a magical jungle with N magical trees, numbered 1..N. He is currently at tree 1, and has to get to tree N where he will escape from the jungle. From each tree there are paths 1 kilometre long to some other trees. There are a total of P paths. Because the trees are magical, it just so happens that for any pair of trees A and B, there will never exist a way (through one or more paths) to get from A to B and from B to A at the same time.
Some of the magical trees have apples on them. Being the greedy bear, Barr wishes to grab apples from all of these trees before he gets to tree N. Each of the paths between the trees have several magical coins on them too. Barr wishes to grab as many of them as possible on his way to tree N.
The speedier bees will catch up with Barr if he travels more than K kilometres. Your task is to maximise the number of coins that Barr grabs on his way to tree N while at the same time keeping Barr away from the bees and collecting all the apples.
Input
On the first line are integers N, P, and K (2 ≤ N ≤ 800, 1 ≤ P ≤ 50,000, 1 ≤ K ≤ 1,000,000,000).
The second line contains an integer F (0 ≤ F ≤ N), the number of trees with apples on them. The next F lines each contains a single integer X (1 ≤ X ≤ N), indicating that tree X has apples on it.
The next P lines each contains three space-separated integers A, B and C (1 ≤ A, B ≤ N, A ≠ B, 1 ≤ C ≤ 1,000), indicating that there exists a path, 1 kilometre long, from tree A to tree B with C coins along it. There will never be more than one path between any two trees.
Output
On the first and only line output an integer
M, the maximum number of coins that Barr can grab while collecting all the apples and escaping from the jungle unharmed. If it is not possible for Barr to collect all the apples and still survive, output -1 instead.
Grading
For 30% of the test cases,
F ≤ 6 and
K ≤ 100.
Sample Input 1
4 5 2
1
2
1 2 1
1 3 100
2 3 100
3 4 100
2 4 1
Sample Output 1
2
Explanation for Sample Output 1
There are 4 trees with connections represented in the above diagram. Tree 2 has apples, and is hence colored. The numbers on the paths are the number of coins on these paths. Barr can travel at most 2 kilometres, otherwise the bees will get him.
Barr has to pass through tree 2. Hence, Barr can either take the paths 1->2, 2->4 or the paths 1->2, 2->3, 3->4 to escape the jungle while collecting all the apples. While the latter paths contain more coins, Barr cannot take them because the distance he has to travel is 3 kilometres. Thus, it is necessary for Barr to take the paths 1->2, 2->4 to escape the jungle before the bees catch him. Barr can hence only collect a measly sum of 2 magical coins.
Sample Input 2
4 4 10
1
3
1 2 1
1 3 100
2 3 100
2 4 1
Sample Output 2
-1
Explanation for Sample Output 2
This time, the bees are slower and Barr can travel up to 10 kilometres. However, after collecting the apples from tree 3, Barr is unable to reach tree 4. Hence, it is impossible for Barr to collect all the apples and escape. Notice that although Barr is able to move from tree 1 to tree 3, he is unable to move from tree 3 to tree 1.