Hillys is in danger! Aliens called the DomZ raid the settlements and steal the citizens. However, most people are waiting for the quick end of the war because they are absolutely sure that elite military forces, Alpha Sections, successfully protect the people of the planet.
Jade, a twenty-year old girl, who belongs to a rebel organization called IRIS Network, could get to the secret Alpha Sections' plant. The rebels think that some important evidence that will reveal the truth and end the war could be photographed in the room numbered n.
Alpha Sections found out that somebody has penetrated into their laboratory, so the evidence will be destroyed in t seconds. Therefore, Jade must do her work in that time. The problem is that the passages between rooms are protected: any passage has its own security level s. The passage that has security level s can be gone through only if one has the security code of level more or equal to s.
Rebels can get any security code that Jade requests, but the higher-level security code costs more money. So Jade should determine what is the minimum level of security code she needs to get the evidence no later that t.
There are multiple test cases. The first line of input is an integer T indicating the number of test cases. For each test case:
First line contains two space-separated integers n and m (2 <= n <= 1000, 1 <= m <= 2000) - the number of rooms and the number of passages between them. At the beginning Jade stands in the room numbered 1, and the room where she must get has number n.
Next m lines describe the passages. Each of these lines contains 4 integers separated by space: xi, yi, di, si (1 <= xi, yi <= n, xi ≠ yi, 1 <= di <= 106, 1 <= si <= 106) - the numbers of rooms that are connected by the ith passage, time needed to go through the passage, and its security level. Each passage is described exactly once. The passages are bidirectional, and it is possible to reach any room from any other room if one has the security code of maximum level.
The last line contains one integer t (0 <= t <= 109) - time at which Jade should get into room n.
If Jade is not able to reach room n in time, even if she has the maximal security level, output "NO" (without quotes).
Otherwise in the first line output "YES", and in the second - two numbers separated by space: the minimal level of security code that makes it possible to get into room n in time no later than t, and the minimal time needed for it.