Farm Cooking
Bessie likes to cook dinner for her fellow cows who are out in the
fields. Bessie just rang the dinner bell to signal them to come in.
Dinner will be ready in T (1 <= T <= 1,000,000) milliseconds, and
Bessie insists that any cows who want to eat dinner with her must
be on time.
The cows are in F (1 <= F <= 100) different fields conveniently
numbered 1..F and connected by P (1 <= P <= 10,000) bidirectional
paths. Bessie is in field 1. Given the time it takes a cow to
walk each path, compute how many different fields are within T
milliseconds of Bessie's cooking. Presume that cows can easily
share a walking path.
PROBLEM NAME: cooking
INPUT FORMAT:
* Line 1: Three space-separated integers: T, F, and P.
* Lines 2..P+1: Each line describes a path between two fields, giving
three space-separated integers, respectively: the field at one
end of the path, the field at the other end, and the time in
milliseconds (1..1,000,000) it takes a cow to walk the path.
SAMPLE INPUT:
1000 5 6
1 2 300
2 4 200
3 4 600
3 4 800
5 3 100
2 5 650
INPUT DETAILS:
Dinner will be ready in 1000 milliseconds. There are 5 fields, with 6
paths between them.
OUTPUT FORMAT:
* Line 1: The number of fields from which cows can reach Bessie in at
most T milliseconds.
SAMPLE OUTPUT:
4
OUTPUT DETAILS:
Cows in fields 1, 2, 4, and 5 can reach Bessie in 1000 milliseconds or
less, but cows in field 3 cannot.