Vào năm 7663, siêu đô thị thông minh aMuaR đưa vào vận hành hệ thống xe tự hành không người lái (AGV) chuyên dùng để vận chuyển các mẫu phẩm y tế và linh kiện bán dẫn tối mật. Hệ thống giao thông của CyberCity gồm có ~n~ nút giao trọng yếu (được đánh số thứ tự từ ~1~ đến ~n~) và ~m~ tuyến đường trên cao hai chiều kết nối trực tiếp giữa các nút giao này. Tuyến đường thứ ~j~ cho phép phương tiện di chuyển từ nút giao ~u_j~ tới nút giao ~v_j~ với thời gian hành trình chính xác là ~w_j~ giây và ngược lại.

Để đảm bảo an toàn tuyệt đối và phân luồng thông minh, tại mỗi nút giao ~u~ đều được trang bị một hệ thống barie thông minh tích hợp đèn tín hiệu giao thông tự động. Cột đèn tại nút giao ~u~ hoạt động tuần hoàn theo hai trạng thái với chu kỳ cố định:

• Đèn xanh sáng liên tục trong ~g_u~ giây.
• Tiếp theo, đèn đỏ sáng liên tục trong ~r_u~ giây.
• Chu kỳ trên lặp lại liên tục: Xanh → Đỏ → Xanh → Đỏ ...

Vào thời điểm ban đầu ~t = 0~, toàn bộ hệ thống giao thông thành phố được kích hoạt đồng bộ. Lúc này, tất cả các nút giao đều bắt đầu ngay vào chu kỳ đèn xanh đầu tiên. Cụ thể, tại nút giao ~u~, trong nửa khoảng thời gian ~[0, g_u)~ đèn sẽ bật màu xanh, trong ~[g_u, g_u + r_u)~ đèn bật màu đỏ, trong ~[g_u + r_u, 2g_u + r_u)~ đèn lại chuyển sang xanh, và cứ thế tiếp diễn.

Xe tự hành phải tuân thủ nghiêm ngặt các quy tắc an toàn vật lý của thành phố:

1. Tại mỗi nút giao có một bãi đỗ đệm an toàn. Xe tự hành chỉ được phép rời khỏi nút giao ~u~ để bắt đầu đi vào một tuyến đường mới tại thời điểm ~t~ nguyên nếu đèn tín hiệu tại nút ~u~ đang ở trạng thái màu xanh.
2. Mỗi khi đèn chuyển sang màu đỏ, các thanh chắn barie vật lý sẽ tự động hạ xuống và khóa chặt các lối ra của nút giao. Nếu xe đến một nút giao mà đèn đang đỏ, xe bắt buộc phải dừng lại ở bãi đỗ đệm và chờ đợi cho đến khi đèn bật sang màu xanh (khi barie mở ra hoàn toàn) thì mới được phép xuất phát tiếp. Xe cũng có thể chủ động chờ nếu điều đó giúp tối ưu hành trình.
3. Khi xe vừa chạm đến nút giao đích ~t~, mẫu phẩm lập tức được tiếp nhận vào kho trung tâm và chuyến hành trình kết thúc ngay tại thời điểm đó (không cần quan tâm trạng thái đèn tín hiệu tại nút giao đích).

Hôm nay, trung tâm điều hành cần điều động một xe tự hành xuất phát từ Trung tâm Kiểm nghiệm tại nút giao ~s~ vào thời điểm ~t = 0~ để vận chuyển khẩn cấp một hộp tạng ghép đến Bệnh viện Đa khoa tại nút giao ~t~. Ban quản lý đảm bảo rằng quy hoạch mạng lưới giao thông luôn cho phép xe tìm được đường đi từ ~s~ đến ~t~.

Hãy tính toán thời gian sớm nhất có thể để xe tự hành hoàn thành nhiệm vụ và có mặt tại nút giao ~t~.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n, m, s, t~ (~2 \le n \le 10^5~, ~1 \le m \le 10^6~, ~1 \le s, t \le n~, ~s \ne t~) — lần lượt là số lượng nút giao, số lượng tuyến đường hai chiều, vị trí xuất phát và vị trí đích đến.
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên ~g_i~ và ~r_i~ (~1 \le g_i, r_i \le 10^{15}~) — thời gian sáng của đèn xanh và đèn đỏ tại nút giao thứ ~i~.
• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa ba số nguyên ~u_j, v_j, w_j~ (~1 \le u_j, v_j \le n~, ~u_j \ne v_j~, ~1 \le w_j \le 10^9~) — mô tả một tuyến đường hai chiều giữa nút giao ~u_j~ và ~v_j~ với thời gian di chuyển là ~w_j~ giây.

Lưu ý: Dữ liệu có thể chứa nhiều tuyến đường giữa cùng một cặp nút giao.

Output

• In ra một số nguyên duy nhất — thời điểm sớm nhất (tính bằng giây) mà xe tự hành có thể đến được nút giao ~t~.

Subtask

Thuật toán của bạn sẽ được chấm theo thang điểm 100 với các subtask như sau:

• Subtask 1 (10 điểm): ~n \le 10~, ~m \le 20~, ~w_j \le 10~, ~g_i, r_i \le 10~.
• Subtask 2 (20 điểm): ~g_i = 10^{15}~ với mọi ~1 \le i \le n~.
• Subtask 3 (20 điểm): ~m = n - 1~.
• Subtask 4 (20 điểm): ~n \le 1000~, ~m \le 2000~.
• Subtask 5 (30 điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 4 1 4
4 3
3 2
5 5
2 2
1 2 3
2 4 4
1 3 5
3 4 2

Sample Output 1

9

Explanation

• Lộ trình 1 (~1 \to 2 \to 4~):
  • Tại ~t = 0~, xe xuất phát ngay từ nút ~1~ (đèn xanh ~[0, 4)~). Di chuyển sang nút ~2~ mất ~3~ giây → đến nút ~2~ tại ~t = 3~.
  • Chu kỳ đèn tại nút ~2~ (~g_2 = 3, r_2 = 2~): Xanh trong ~[0, 3)~, Đỏ trong ~[3, 5)~, Xanh trong ~[5, 8), \dots~
  • Tại ~t = 3~, đèn tại nút ~2~ vừa chuyển sang màu đỏ. Xe phải đợi tại nút ~2~ trong ~2~ giây (từ ~t = 3~ đến ~t = 5~).
  • Đúng thời điểm ~t = 5~, đèn chuyển xanh, xe xuất phát từ nút ~2~ sang nút ~4~ với thời gian di chuyển ~4~ giây → xe đến đích ~4~ tại thời điểm ~t = 5 + 4 = 9~.
• Lộ trình 2 (~1 \to 3 \to 4~):
  • Xuất phát từ nút ~1~ lúc ~t = 0~, đi sang nút ~3~ mất ~5~ giây → đến nút ~3~ tại ~t = 5~.
  • Chu kỳ đèn tại nút ~3~ (~g_3 = 5, r_3 = 5~): Xanh trong ~[0, 5)~, Đỏ trong ~[5, 10), \dots~
  • Tại ~t = 5~, đèn tại nút ~3~ chuyển đỏ. Xe phải đợi đến ~t = 10~.
  • Tại ~t = 10~, xe rời nút ~3~ sang ~4~ mất ~2~ giây → đến đích lúc ~t = 10 + 2 = 12~.

Lộ trình 1 cho thời gian đến đích sớm nhất tại thời điểm ~t = 9~.