Thriving Plants

You are given N plants and M symbiotic relationships among them. Each plant initially requires 1 unit of sunlight. Every relationship connects two plants and adds an extra sunlight cost if one plant depends on the other. Using these relationships, you can compute the minimum sunlight needed for each plant in a way similar to Dijkstra's algorithm. A plant is considered to be thriving if its minimum sunlight requirement is at most \(10^4\) (i.e. 10000). Your task is to determine the maximum number of plants that can thrive.

inputFormat

The first line of input contains two integers N and M, where N is the number of plants and M is the number of symbiotic relationships.

Each of the following M lines contains three integers: a, b, and c. These denote that there is a symbiotic relationship between plant a and plant b (with plants numbered from 0 to N-1) which adds an extra sunlight requirement of c units.

outputFormat

Output a single integer on a new line – the maximum number of plants that can thrive (i.e. the number of plants whose minimum sunlight requirement is at most 10000).

4 3
0 1 2
1 2 1
3 0 4

4