"Tết tết tết tết đến rồi, tết tết tết tết đến rồi" - câu hát rất quen thuộc của mọi nhà mỗi dịp Tết đến, xuân về. Đó là với mọi người, còn với phuongman thì không, tại vì Tết thì đến rồi nhưng manthibichloi vẫn chưa đến đón phuongman đi chơi Tết. phuongman quyết định sẽ dỗi "người ấy" của mình.

Vì để có thể ~~làm phuongman hết dỗi mặc dù không tự nguyện~~ đi chơi với phuongman sớm nhất có thể, manthibichloi cần chọn con đường ngắn nhất để có thể đến nhà "người ấy". Trong thành phố nơi hai người ở, có \(n\) địa điểm, nhà của phuongman ở vị trí \(n\) còn nhà của manthibichloi ở vị trí \(1\). Trong thành phố có \(m\) con đường nối với nhau, các con đường này có thể đi theo cả hai hướng, con đường thứ \(i\) nối hai địa điểm \(u_{i}\) và \(v_{i}\), khi đi hết con đường đó tốn một khoảng thời gian là \(t_{i}\) giây. Tuy nhiên, con đường nào cũng cần phải trả phí, vì thế anh ta muốn chọn con đường ngắn nhất và phí phải trả là ít nhất. Con đường thứ \(i\) sẽ ngốn của anh ta một khoản tiền có giá trị bằng \(c_{i}\). manthibichloi chỉ có thể đi trên con đường thứ \(i\) nếu hiện tại anh ấy có lượng tiền trong ví lớn hơn hoặc bằng \(c_{i}\). Ban đầu, trước khi đi, ví của manthibichloi có tất cả \(k\) đồng, đây cũng là số tiền tối đa manthibichloi có thể để trong ví. Ở bất cứ địa điểm nào, manthibichloi đều có thể đến cây ATM để rút tiền. Mỗi lần rút tiền ở cây ATM, anh ta có thể rút một lượng tiền bất kì, miễn sao cho lượng tiền đó khi bỏ vào ví sẽ không vượt quá \(k\) đồng. Mỗi lần rút tiền sẽ tốn của anh ấy \(1\) giây.

Yêu cầu: Tìm lượng thời gian nhỏ nhất có thể để manthibichloi có thể đến được nhà phuongman, trong những đường đi có thời gian ít nhất, tìm đường đi có số tiền mà sau khi đi trong ví còn nhiều tiền nhất. Nếu không tồn tại đường đi thì in ra -1 -1.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) (\(n \le 5 \times 10^4\), \(m \le 5 \times 10^5\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên biểu diễn một con đường (\(1 \le u,v \le n, 0 \le t \le 10^4, 0 \le c \le 10^3\)).
• Dòng cuối cùng là một số nguyên dương \(k\) (\(\max(c_{i}) \le k \le 10^3\)).

Output

• In ra hai số nguyên, lần lượt là thời gian ngắn nhất và số tiền trong ví sau khi đi hết con đường.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): \(c_{i} = 0\) với mọi \(i = 1, 2, 3..., m\).
• Subtask \(3\) (\(30\%\) số điểm): không có ràng buộc gì thêm.

Example

7 7
2 1 2 1
2 4 2 1
4 3 2 1
4 5 1 1
2 5 3 1
5 6 2 1
7 6 8 1
3

16 2