Bình đang đi du lịch tự túc qua \(N\) địa điểm và \(M\) tuyến đường một chiều. Một số tuyến đường được khuyến mãi hoàn tiền hoặc tặng phiếu xăng nên chi phí có thể nhận giá trị âm.

Hãy tìm hành trình ngắn nhất từ địa điểm \(S\) đến \(T\). Đồng thời, in ra danh sách các địa điểm đi qua trên hành trình này. Nếu có nhiều hành trình cùng chi phí tối ưu, Bình muốn ưu tiên hành trình đi qua ít địa điểm nhất.

Định dạng đầu vào

• Dòng đầu chứa bốn số nguyên \(N\), \(M\), \(S\), \(T\) (\(1 \le N \le 1000\), \(0 \le M \le 2000\), \(1 \le S, T \le N\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u\), \(v\), \(w\) (\(1 \le u, v \le N\), \(-100 \le w \le 1000\)).

Định dạng đầu ra

• Nếu không thể di chuyển từ \(S\) tới \(T\), in ra unreachable.
• Ngược lại:
  • Dòng 1: Chi phí tối thiểu.
  • Dòng 2: Số địa điểm \(L\) trong hành trình.
  • Dòng 3: Dãy \(L\) số nguyên cách nhau bởi khoảng trắng là các địa điểm theo thứ tự đi qua.

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 100\), \(M \le 200\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input:

3 3 1 3
1 3 10
1 2 5
2 3 5

Output:

10
2
1 3

Giải thích: Hai hành trình \(1 \to 3\) và \(1 \to 2 \to 3\) đều có chi phí tối thiểu là 10. Ta ưu tiên hành trình đi qua ít địa điểm nhất (\(1 \to 3\) có 2 địa điểm).