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.

Yêu cầu: Tìm giá trị nhỏ nhất của độ nguy hiểm lớn nhất và lượng nhiên liệu ít nhất tương ứng.

Input

• 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}~).

Output

• Ghi 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.