One of the reasons why Jeffrey is so scared of roads is that Frank is able to drive on them. Frank is not a very talented driver; in fact, he is one of the worst. However, Frank believes that he won't cause any accidents if the distance he drives is under kilometres.

Today, Frank needs to buy some apples. From his house, he plans to drive his car on the roads that Jeffrey is scared of in order to get to a Food Basics. To ensure that Frank doesn't cause any accidents, Frank will only visit a Food Basics that is under kilometres from his house. Help Frank find all of the Food Basics that he can visit.

#### Input Specification

The first line of input will contain four integers, , the number of kilometres that Frank can drive without seriously injuring someone, , the number of buildings that Frank can visit, , the number of roads that Frank can drive on, and , the number of Food Basics near Frank's house.

The next lines will contain an integer , denoting the buildings that are a Food Basics. Frank's house will never be a Food Basics. Who would want to live in a grocery store?

We define a road as a connection from one building to another. Each building is marked with a number from to . Frank's house will be denoted by the integer . The next lines will be in the form `A B L`

, denoting a road that travels from building to building of length kilometres. The road can only be traveled in one direction.

#### Output Specification

Output the number of Food Basics that Frank can visit, within kilometres from his house.

#### Sample Input

```
15 3 5 2
2
3
0 1 2
1 2 10
1 3 20
0 3 22
0 2 15
```

#### Sample Output

`1`

#### Explanation

Shortest distance from Frank's house to building 2 is 12. Shortest distance from Frank's house to building 3 is 22. The only Food Basics reachable from Frank's house is building 2.

## Comments

I'm pretty sure that existing solutions have been subject to fairly weak test data. The following case whose answer is

`1`

will fail solutions that count stores kilometers away from Frank's house:An incorrect solution in this respect will output

`2`

. I have seen a couple of solutions which have received AC so far that do this.As such, would it be possible to include the above case in the test data?

i think this is a pretty misleading comment.

a path to a food basics that is exactly T kilometres away is considered a valid path, so the correct output for ur test case is indeed 2 and not 1.to be fair the question itself is very unclear, stating that a path has to be "under T kilometres", twice. thankfully the editorial is correct in saying that it is actually just supposed to be "no more than T km"

i am saying this because i originally had "<t" and had 6 test cases WA, but then changed it to "<=t" and got all AC

please correct me if im wrong

I don't understand why my dijkstra's isn't working. It worked with a previous problem, so I don't understand why it isn't working now. Could someone check my code, please?

nvm

Optimize my BFS?How can I make my BFS faster? I'm TLE'ing the larger test cases and I'm pretty sure it's because my BFS repeats certain roads due to certain paths being faster than others yet being checked after the slower ones. Is there a way to speed things up?

EDIT:Nvm I AC'd after a few more changes.Two times, is stated to be the exclusive limit. It is inclusive.

What are the bounds on

Also can someone please explain to me how

`memset`

works.contrary to the problem statement

is not necessarily ≤

Test data is fixed (probably). Comment again if you find any issues. All submissions are rejudged.

Is it guaranteed to be no more than one road between each pair of buildings?

Don't assume anything not explicitly mentioned.

The problem says L <= T but you have L = 20 and 22 while T = 15

Fixed.