Bạn là một ninja đang lẻn vào một dinh thự khổng lồ. Dinh thự gồm các sảnh hình vuông giống hệt nhau, xếp đều theo các hướng Bắc, Nam, Đông, Tây thành một lưới ô vuông.

Dù đã được huấn luyện kỹ lưỡng, bạn chỉ có thể di chuyển theo một số lối nhất định vì dinh thự được canh phòng nghiêm ngặt. Chính giữa mỗi bức tường trong bốn bức tường của một sảnh có một cửa nối với sảnh kề bên. Trong mỗi sảnh có \(N\) vị trí an toàn để ẩn nấp, bao gồm cả bốn vị trí cửa. Ngoài ra, mỗi sảnh có \(M\) lối đi an toàn nối các vị trí an toàn với nhau. Bạn chỉ được di chuyển trong sảnh theo những lối đi này. Thời gian di chuyển trên mỗi lối đi được cho trước, và cấu trúc các vị trí, lối đi cùng thời gian tương ứng giống nhau trong mọi sảnh.

Ban đầu, bạn ở vị trí an toàn \(V\) trong một sảnh; vị trí này không phải cửa. Đích đến là vị trí an toàn \(W\), cũng không phải cửa, trong sảnh cách sảnh ban đầu \(X\) sảnh về phía Đông và \(Y\) sảnh về phía Bắc. Giá trị âm của \(X\) hoặc \(Y\) tương ứng với hướng Tây hoặc Nam.

Không tính thời gian đi qua cửa để sang sảnh kề bên và thời gian ẩn nấp tại một vị trí an toàn. Dinh thự đủ lớn để bạn không bao giờ đi ra ngoài phạm vi của nó.

Yêu cầu

Cho thông tin dinh thự, hãy xác định có thể đến đích hay không. Nếu có thể, hãy tìm thời gian ít nhất để đến đích.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa sáu số nguyên \(N,M,V,X,Y,W\). Trong mỗi sảnh, các vị trí an toàn được đánh số từ \(1\) đến \(N\). Các cửa trên tường phía Đông, Bắc, Tây, Nam lần lượt mang số \(1,2,3,4\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,T_i\). Trong mỗi sảnh, có thể đi theo cả hai chiều giữa vị trí an toàn \(A_i\) và \(B_i\) bằng một lối đi an toàn, mất \(T_i\) giây.

Các số trên cùng một dòng được phân cách bởi dấu cách. Không có lối đi nối một vị trí với chính nó, và không có hai lối đi nối cùng một cặp vị trí, kể cả khi đảo thứ tự hai đầu mút.

Dữ liệu ra

Ghi ra đầu ra chuẩn thời gian ít nhất, tính bằng giây, để đến đích. Nếu không thể đến đích, in ra -1.

Ràng buộc

• \(5\le N\le100\,000\).
• \(1\le M\le200\,000\).
• \(5\le V\le N\) và \(5\le W\le N\).
• \(|X|\le1\,000\,000\,000\) và \(|Y|\le1\,000\,000\,000\).
• \(1\le A_i,B_i\le N\), \(A_i\ne B_i\) và \(1\le T_i\le1000\) với mọi \(1\le i\le M\).
• Với mọi \(i\ne j\), \((A_i,B_i)\ne(A_j,B_j)\) và \((A_i,B_i)\ne(B_j,A_j)\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(|X|\le3\) và \(|Y|\le3\).

Ví dụ

7 9 5 1 0 6
1 2 1
1 5 4
2 3 2
3 6 5
4 5 2
4 6 3
4 7 1
5 6 2
6 7 1

7

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

-1