Path Within Weight Limit

You are given an undirected graph with n nodes and m weighted edges. In addition, you are provided with two distinct nodes, s (start) and t (target), and a weight limit W. Your task is to determine whether there exists a path from node s to node t such that the sum of the weights of the edges along the path does not exceed W.

Formally, let the weight of a given path be \(\sum_{e \in path} weight(e)\). You need to decide if there exists a path from s to t satisfying \(\sum_{e \in path} weight(e) \leq W\).

Note: The graph is undirected, and there might be no direct edge between the two nodes. Also, if there are no edges, the answer is "NO" unless s equals t, which is not considered in this problem.

inputFormat

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

n m W s t
u1 v1 w1
u2 v2 w2
... 
um vm wm

Where:

• n is the number of nodes.
• m is the number of edges.
• W is the maximum allowed total weight.
• s and t are the start and target nodes respectively.
• Each of the next m lines contains three integers u, v, and w indicating there is an undirected edge between nodes u and v with weight w.

outputFormat

Output a single line to stdout containing either "YES" if there exists a path from s to t whose total weight is at most W, or "NO" otherwise.

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

YES