Minimum Signal Amplifiers in a Tree Network

A tree network is an acyclic connected network in which there is exactly one communication path between any two nodes. In the network, one special node acts as the server and sends out a signal with an initial strength S to all other nodes. When a signal travels along an edge with an attenuation value d, its strength decreases by d. That is, if a node receives a signal with strength v and forwards it along an edge with attenuation d, the receiving node gets a signal of strength v - d (provided that v - d > 0). If the resulting signal strength is not positive, then the signal cannot be forwarded along that edge.

One remedy for signal decay is to install a signal amplifier at some nodes. A signal amplifier boosts a received signal (with strength > 0) back to the original strength S. However, for simplicity, each node processes the signal only once; if the same node receives the signal a second time, it ignores it.

Your task is: Given a tree network, determine the minimum number of signal amplifiers that need to be installed so that every node in the network can receive the signal from the server.

For example, consider a network with S = 4 and edges as shown below. Without any amplifier, the server sends a signal to node a (edge attenuation 3), so node a receives a signal of strength $$4-3=1$$. Then node a sends the signal to node b, but the edge attenuation is 2, so the signal would have strength $$1-2=-1$$ and would not reach node b. However, if an amplifier is installed at node a, then after receiving signal 4 (from the server) it is amplified to 4, and the subsequent transmission to b will be successful (4-2=2 > 0).

Input/Output Format: See below.

inputFormat

The first line contains two integers n and S, where n (2 ≤ n ≤ 10⁵) is the number of nodes in the tree and S (S ≥ 2) is the initial signal strength.

Each of the following n-1 lines contains three integers u, v, and d (1 ≤ d < S) representing an undirected edge between nodes u and v with attenuation value d. The server is always node 1.

outputFormat

Output a single integer representing the minimum number of signal amplifiers that need to be installed so that every node can receive the signal from the server.

sample

3 4
1 2 3
2 3 2

1