Max Unique Islands

You are given a collection of islands connected by canals. Each canal connects two islands and has an associated travel distance. Starting from a specified island, your task is to determine the number of unique islands that can be reached such that the total travel distance from the starting island is at most \(d\). In other words, count the islands for which the minimum travel distance from the starting island is \(\le d\).

The problem guarantees that all travel distances are positive. The canals allow bidirectional travel.

Input Format: The first line contains four integers \(n\), \(m\), \(d\), and \(s\) representing the number of islands, the number of canals, the maximum travel distance, and the starting island respectively. The next \(m\) lines each contain three integers \(u\), \(v\), and \(l\) indicating that there is a canal between islands \(u\) and \(v\) with travel distance \(l\).

Output Format: Output a single integer representing the maximum number of unique islands that can be visited without exceeding the travel distance \(d\).

inputFormat

The input is read from standard input and is formatted as follows:

n m d s
u1 v1 l1
u2 v2 l2
... 
um vm lm

Where:

• \(n\) is the number of islands.
• \(m\) is the number of canals.
• \(d\) is the maximum travel distance allowed.
• \(s\) is the starting island.
• Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(l\) representing a canal between islands \(u\) and \(v\) with travel distance \(l\).

outputFormat

Output a single integer: the number of islands that are reachable from the starting island \(s\) with a total travel distance not exceeding \(d\).

## sample

4 4 10 1
1 2 4
2 3 2
3 4 3
4 1 3

4