Islands Travel Within Budget

You are given a collection of n islands connected by m bidirectional bridges. Each bridge has a travel cost. Your task is to determine whether it is possible to travel from a specified starting island to a destination island without exceeding a given maximum travel cost k. More formally, if you choose a path P from the start to the destination, let the total cost of the path be \(\sum_{e \in P} cost(e)\). You need to decide if there exists a path such that \(\sum_{e \in P} cost(e) \leq k\).

Note: The bridges allow bidirectional travel, meaning you can go from island \(u\) to island \(v\) and back from \(v\) to \(u\) with the same cost.

inputFormat

The input is given from stdin and has the following format:

1. The first line contains three integers n, m, and k, where:
• n (\(1 \le n \le 10^5\)) is the number of islands.
• m (\(0 \le m \le 10^5\)) is the number of bridges.
• k (\(1 \le k \le 10^9\)) is the maximum allowed total cost.
2. The next m lines each contain three integers u, v, and w, representing a bidirectional bridge connecting islands u and v with cost w.
3. The last line contains two integers start and end indicating the starting island and the destination island.

outputFormat

Output a single line to stdout containing YES if it is possible to travel from the starting island to the destination island with a total cost no more than k, or NO otherwise.

5 6 15
1 2 3
1 3 10
2 4 7
3 4 5
3 5 1
4 5 3
1 5

YES