Bạn đang leo dốc trong một thành phố trên núi.

Nơi thành phố bạn sống đặc biệt có những con đường cao tít tựa Đà Lạt. ~N~ căn nhà nơi đây có thể đến được với nhau bằng ~M~ con đường hai chiều, con đường thứ ~i~ có độ dài ~w_i~ và độ cao là ~c_i~. Căn nhà cuối cùng (thứ ~N~) trên đỉnh núi là nơi bạn cần đến, từ căn nhà số ~1~ bạn cần đến đó nhanh nhất có thể nhưng điều đó không thành vấn đề vì bạn đã quá rành đường nơi đây rồi.

Điều bạn cần là tìm con đường có thể tối đa hoá độ cao giữa đường cao nhất và đường thấp nhất mà vẫn đảm bảo về thời gian, bởi leo trèo là việc bạn thích nhất. Liệu bạn có biết chênh lệch tối đa đó không?

Input

• Dòng đầu tiên gồm hai số nguyên dương là ~N~ và ~M~ (~1 \leq N \leq 2 \cdot 10^5, 1 \le M \leq 3 \cdot 10^5~).

• ~M~ dòng tiếp theo dòng thứ ~i~ gồm bốn số ~u_i~, ~v_i~, ~w_i~, ~c_i~ (~1 \leq u_i \neq v_i \leq N~, ~1 \leq w_i, c_i \leq 10^9~) lần lượt cho biết độ dài và độ cao của con đường nối hai địa điểm ~u_i~ và ~v_i~. Giữa hai địa điểm không có quá một con đường.

Đề đảm bảo luộn tồn tại đường đi từ ~1~ đến ~N~.

Output

Ghi ra một số duy nhất cho biết chênh lệch lớn nhất bạn cần mà vẫn đảm bảo thời gian di chuyển là ngắn nhất.

Scoring

Sample Input 1

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

Sample Output 1

6