Sau khi cướp hết ngân hàng, thì Catalina cùng Claude đã đi tới Liberty City. Chỉ còn CJ ở lại. CJ giờ cũng chẳng biết làm gì, và đi dạo đâu đó chơi. Trong lúc đi dạo, vô tình gặp ông The Truth. Và hai người bắt tay với nhau làm bạn, và cùng nhau tới thành phố San Fierro làm ăn với chiếc xe buýt của ông. Trong lúc đi thì ông chợt nhận ra là ở thành phố này chủ yếu là đường hầm, ông thì chưa đo độ cao chiếc xe ?!!. Và ông đã đưa cho CJ tấm bản đồ San Fierro.

Thành phố San Fierro có \(N\) địa điểm, đánh số từ \(1\) tới \(N\), và \(M\) con đường có hầm, được đánh số từ \(1\) tới \(M\), con đường thứ \(i\) có độ dài là \(L_{i}\), độ cao giới hạn là \(H_{i}\). Xe của ông hiện tại ở địa điểm \(s\), và muốn tới địa điểm \(t\). Và ông quyết định nhờ CJ tìm đường đi mà độ cao đạt được là lớn nhất có thể để đi qua. Trong các đường đi có cùng độ cao lớn nhất, thì ông muốn lấy đường đi ngắn nhất có thể.

Hãy chỉ ra cho CJ con đường thoả mãn điều kiện của ông The Truth. Nếu có nhiều đường đi thoả mãn, in ra một đường đi bất kỳ.

Input

• Dòng đầu tiên chứa bốn số nguyên dương \(N,M,s,t\) (\(1 \leq s,t \leq N, s \neq t\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên dương \(u_{i},v_{i}, L_{i},H_{i}\) (\(1 \leq u_{i},v_{i} \leq N, u_{i} \neq v_{i},1 \leq L_{i},H_{i} \leq 10^{9}\)).

Output

• Gồm 2 dòng:
• Dòng đầu tiên ghi ra độ cao lớn nhất có thể.
• Dòng thứ hai ghi ra số hiệu trên đường đi tương ứng có độ dài nhỏ nhất theo thứ tự hành trình, bắt đầu từ \(s\) và kết thúc tại \(t\).

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 2.10^{5}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{3}\), \(M \leq 2.10^{3}\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

3
4 5 3