Trùm khủng bố B.L. trốn tránh sự truy đuổi của cảnh sát ở một hệ thống cống thoát nước ngầm của thành phố. Hai đoạn đường ống bất kỳ trong hệ thống cống có nhiều nhất một nút chung là đầu mút chung cho cả hai. Tên khủng bố ẩn nấp tại một trong những nút như vậy. Để ngăn cản sự truy bắt của cảnh sát tên khủng bố đã đặt bom hẹn giờ tại một số nút. Việc đi qua nút như vậy là không thể thực hiện được sau khi bom phát nổ. Cảnh sát Bondy muốn bắt tên khủng bố này. Trong tay Bondy có sơ đồ của hệ thống cống ngầm, trong đó chỉ rõ vị trí nút mà tên khủng bố ẩn nấp và vị trí các nút có đặt bom và thời điểm hẹn phát nổ của chúng. Tại thời điểm ~ 0 ~ Bondy bắt đầu cuộc truy đuổi từ một nút xuất phát và muốn đến được nút ẩn nấp của tên khủng bố sau thời gian nhanh nhất. Bondy sẽ hy sinh nếu bom nổ đúng lúc anh ta đi qua nút chứa nó, trái lại anh ta sẽ không bị tổn thương và có thể tiếp tục truy đuổi.

Yêu cầu: Xác định thời gian nhỏ nhất cần thiết để Bondy có thể bắt được tên khủng bố, nếu như điều đó có thể thực hiện được.

Dữ liệu vào

• Dòng đầu tiên chứa các số nguyên dương ~ n, m, s, t ~. ~ n ~ là số lượng nút, các nút được đánh số từ 1 đến ~ n ~. ~ m ~ là số lượng đoạn đường ống. Giữa hai nút bất kỳ có nhiều nhất là một đoạn đường ống. ~ s ~ là chỉ số của nút xuất phát của Bondy và ~ t ~ là nút mà tên khủng bố ẩn nấp. ~ (1 ≤ s, t ≤ n ≤ 100; 1 ≤ m ≤ n^2 ) ~.
• Dòng thứ ~ i ~ trong số ~ n ~ dòng tiếp theo chưa số ~ 0 ~ nếu nút này không có bom và chứa số nguyên dương ~ x_i ~ cho biết thời điểm phát nổ của quả bom ở nút ~ i ~ ~ ( i = 1, 2, ..., n) ~.
• Mỗi dòng trong số ~ m ~ dòng tiếp theo chứa chỉ số của hai đầu mút của một đoạn đương ống và số nguyên dương ~ y ~ là thời gian cần thiết để đi từ đầu này đến đầu kia của đoạn đường ống này. ~ (y ≤ 1000) ~.

Kết quả

Ghi ra thời gian nhỏ nhất mà Bondy cần có để bắt giữ tên khủng bố nếu như việc đó có thể thực hiện được (như vậy, sẽ ghi ~ 0 ~ nếu Bondy xuất phát tại nút mà tên khủng bố ẩn nấp). Trái lại cần ghi ~ -1 ~.

Ví dụ:

Input 1

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

Output 1

8 

Input 2

3 2 1 3
0
1
0
1 2 3
2 3 1 

Output 2

-1