The Neighbor#233

The Neighbor

1 second

64 megabytes

Medium

Ivan Ivanovich has been living in a sanatorium for a week. He shares a double room with Petr Petrovich. Everything was fine until one day, Ivan Ivanovich returned to his room and found the door closed. "Petr Petrovich must have taken the key!" Ivan Ivanovich realized (since there was only one key for both of them).

The situation was desperate. Absent-minded Petr Petrovich might forget where he lives and not return. The only hope is to find Petr Petrovich and take the key from him. Fortunately, Ivan Ivanovich knows all the places where Petr Petrovich usually stays, and the routes between them. However, Ivan Ivanovich has poor eyesight and can see Petr Petrovich only if they are at exactly the same position (that is, at the same place or at the same position on a route).

Ivan Ivanovich tells you all of Petr Petrovich's favorite places and routes, as well as their maximal speeds. He now asks whether, in all possible cases, he can catch Petr Petrovich.

For example, Ivan Ivanovich lives on the third floor at point $4$ . Petr Petrovich may go to the hall on the third floor (point $3$ ), then to the hall on the second floor (point $2$ ), and then to the hall on the first floor (point $1$ ). In that case, Ivan Ivanovich is guaranteed to eventually meet Petr Petrovich, traveling from point $4$ to point $1$ via points $3$ and $2$ .

Input

The first line contains the number of test cases $K$ ( $K < 25$ K < 25). The following lines contain the data for each test case.

The first line of each test case contains two integers: the number of points $N$ ( $1 \leq N < 100$ 1 \leq N < 100) and the number of routes $M$ ( $0 < M < 1000$ 0 < M < 1000). The next $M$ lines each contain three integers separated by spaces: the start point, the end point, and the length (in meters) of the route. Each route length is at least $1$ meter and at most $1000$ meters. Routes are bidirectional, so a route from $x$ to $y$ is the same as a route from $y$ to $x$ . There are no routes of the form $x \to x$ x \to x (no loops), and there cannot be two routes with the same pair of endpoints. The routes are not necessarily straight, and they may only intersect at endpoints. It is possible to get from any point to any other (possibly via other points).

The last line of each test case contains two integers separated by a space: the maximal speed of Ivan Ivanovich $V_{I I}$ V_{II} and the maximal speed of Petr Petrovich $V_{P P}$ V_{PP} (in kilometers per hour), where $0 < V_{I I} < 15$ 0 < V_{II} < 15, $0 < V_{P P} < 15$ 0 < V_{PP} < 15.

Output

For each test case, output on a separate line YES if Ivan Ivanovich can, regardless of Petr Petrovich's movements, eventually meet him in finite time. Otherwise, output NO.

Examples

Example 1