GRAPH

Trên bản đồ thành phố HP có $n$ địa điểm (đánh số từ $1$ đến $n$) và $m$ con đường hai chiều (đánh số từ $1$ đến $m$), con đường $i$ ($1\le i\le m$) nối giữa hai địa điểm $u_i$ và $v_i$ ($1\le u_i,v_i\le n$; $u_i\ne v_i$) có độ nguy hiểm là $p_i$ và tiêu tốn nhiên liệu $w_i$.

Hải muốn di chuyển từ địa điểm $1$ đến địa điểm $n$ sao cho độ nguy hiểm lớn nhất là nhỏ nhất và trong số những cách di chuyển có độ nguy hiểm lớn nhất là nhỏ nhất đó thì chọn cách đi tốn ít nhiên liệu nhất.

Độ nguy hiểm lớn nhất của một cách di chuyển là giá trị $p_i$ lớn nhất trong các con đường đi qua; lượng nhiên liệu là tổng các $w_i$ của các con đường đi qua. Giữa hai địa điểm có thể có nhiều con đường.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương $n,m$ ($1\le n\le 2\times {10}^5$, $1\le m\le 3\times {10}^5$);
• $m$ dòng sau, mỗi dòng gồm bốn số nguyên dương $u_i,v_i,p_i,w_i$ mô tả một con đường nối giữa hai địa điểm $u_i$ và $v_i$; có độ nguy hiểm là $p_i$ ($1\le p_i\le {10}^{18}$) và tiêu tốn nhiên liệu $w_i$ ($1\le w_i\le 5\times {10}^{12}$).

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn có thể di chuyển từ địa điểm $1$ đến địa điểm $n$.

Dữ liệu ra

In ra hai số nguyên theo thứ tự là giá trị nhỏ nhất của độ nguy hiểm lớn nhất khi di chuyển từ địa điểm $1$ đến địa điểm $n$ và lượng nhiên liệu ít nhất trong số tất cả các cách di chuyển có độ nguy hiểm lớn nhất là nhỏ nhất. Hai số ghi cách nhau bởi dấu cách.

Ràng buộc

• $1\le n\le 2\times {10}^5$, $1\le m\le 3\times {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le p_i\le {10}^{18}$, $1\le w_i\le 5\times {10}^{12}$

Subtasks

• Subtask 1 ($8\%$ số điểm): $n\le 6$, $m\le 10$.
• Subtask 2 ($32\%$ số điểm): $n\le {10}^4$, $m\le 2\times {10}^4$, $w_i=1$.
• Subtask 3 ($18\%$ số điểm): $p_i=1$.
• Subtask 4 ($20\%$ số điểm): $n\le {10}^4$, $m\le 2\times {10}^4$.
• Subtask 5 ($22\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ