J. Judging Gifts
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Your birthday is approaching and you are expecting a gift from your friend. You don't really care about what gift you receive, but it is important to you how much effort was put into it.

Initially, your friend has some item $$$x$$$. He is not the only one looking for a perfect birthday present. Therefore, he can trade his item for another item, but it takes some effort to do so. As one gift exchange might not be enough to find the perfect gift, this can be done multiple times.

On your birthday you receive item $$$y$$$ as a gift. It is important to you that your friend put in total at least $$$k$$$ effort into the gift exchange. Clearly, it would be considered rude to ask him about his initial item or the gift exchanges he made. In good faith you only want to know if it is possible that your friend put at least $$$k$$$ effort into the gift exchanges.

Input

Each test contains multiple test cases. The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$, the number of test cases. The description of the $$$t$$$ test cases follow.

The first line of each test case contains four integers $$$n, m, k, y$$$ $$$(1 \le n \le 10^5, 0 \leq m \leq 10^5, 1 \leq k \leq 10^9, 1 \le y \le n)$$$, the number of different gifts, the number of possible gift exchanges, the minimum effort you expect to be put into the gift exchange and the gift you receive.

The next $$$m$$$ lines of each test case contain two integers $$$u_i, v_i, e_i$$$ $$$(1 \leq u_i, v_i \leq n, 1 \leq e_i \leq 10^9)$$$, meaning that gift $$$u_i$$$ can be exchanged for gift $$$v_i$$$ with effort $$$e_i$$$. It is guaranteed that $$$u_i \not = v_i$$$ and the ordered pair $$$(u_i, v_i)$$$ does not appear more than once. You are allowed to use the same gift exchange multiple times.

It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$10^5$$$ respectively.

Output

For each test case, output "YES" if it is possible that your friend put at least $$$k$$$ effort into the gift exchange and output "NO" otherwise.

Example
Input
2
5 5 9 4
5 4 6
4 1 3
1 3 7
3 2 1
2 1 2
8 7 7 2
1 2 1
3 2 3
5 3 3
7 5 2
7 6 4
6 4 5
1 4 2
Output
NO
YES