Description

Suppose that there is a country that consists of N towns. A number between 1 and N is given to each town. They are connected with the bi-directional roads, and when someone wants to move between different towns, he/she must pass the road. It takes different time to pass according to the road. At this point, a restaurant at the town 1 is going to deliver the food to each town. Among N towns, the restaurant wants to receive the order from towns where delivery can be done with less than K time. The following is an example when N = 5 and K = 3.

배달_1_uxun8t.png

In the above figure, the restaurant at the town 1 can deliver the food to the town [1, 2, 4, 5] with less than 3 time. But, since there is no way to deliver food th town 3 with less than 3 times, the restaurant does not receive an order from town 3. Therefore, the number of towns where the restaurant at the town 1 receives an order is 4.
Given the number of towns N, the information of road that connects each town road, and the target delivery time K as parameters, write a function solution to return the number of towns where the restaurant accepts an order.

Constraints
  • The number of towns N is a natural number between 1 and 50.
  • Length of road (the number of road's information) is between 1 and 2,000.
  • Each element of road indicates the information of each road that connects the towns.
  • road is an array with a length of 3, and represents (a, b) in turn.
    • a and b (1 ≤ a, b ≤ N, a != b) are the town's number that connected by the road, and c (1 ≤ c ≤ 10,000, c is a natural number) indicates the time required to pass the road.
    • There may be several roads connecting town a and b.
    • The information of a road is not given more than twice.
  • K represents the time where food can be delivered and is between 1 and 500,000.
  • There is always path to move between any of two towns.
  • Return the number of towns where the restaurant at town 1 can deliver the food with less than K time.

Examples
N road K result
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4
6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4

Example #1
This is the same with the example in the problem statement.

Example #2
Given towns and roads are as shown in the following figure.
배달_3_njc7kq.png
Since the number of towns where the delivery can be done with less than 4 times is 4, town [1, 2, 3, 5], return 4.

Result Stop
Result of [Run] or [Submit] will be displayed here