Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường hai chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và độ đẹp ~b_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~ để dự sự kiện. Là một người đam mê cái đẹp, anh muốn chọn một lộ trình sao cho những con đường anh đi qua có tổng độ đẹp là lớn nhất, tuy vậy do cần tiết kiệm thời gian nên anh sẽ chỉ chọn lộ trình ngắn nhất (tức là tổng độ dài các con đường là bé nhất có thể) để đi từ ~1~ tới ~n~.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất và có tổng độ đẹp lớn nhất mà anh ta có thể đi.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,c_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và độ đẹp ~c_i~.

Output

• Gồm một dòng chứa hai số nguyên ~L~ và ~B~, với ~L~ là độ dài của lộ trình ngắn nhất để đi từ ~1~ tới ~n~ và ~B~ là độ đẹp lớn nhất có thể của các lộ trình có độ dài ~L~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~, in ra ~-1~.

Constraints

• ~1 \le n,m \le 2*10^5~.
• ~1 \le l_i,c_i \le 10^9~.

Subtasks

• Subtask ~1~: ~1 \le n,m \le 20~ ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

5 6
1 5 8 9
1 2 3 2
2 5 3 4
1 3 1 1
3 4 1 5
4 5 4 1

Sample Output 1:

6 7

Explanation 1:

Có hai lộ trình có độ dài ~6~ có thể đi là ~(1,2,5)~ và ~(1,3,4,5)~. Trong đó lộ trình ~(1,3,4,5)~ có độ đẹp lớn nhất là bằng ~7~.

Sample Input 2:

4 2
1 2 1 1
1 3 1 1

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~.