Du lịch NewYork

Mùa hè này, Nam vừa trúng tuyển đại học với số điểm cao và cậu ấy được ba mẹ thưởng cho một
chuyến du lịch tại thành phố NewYork, Mỹ. Thành phố này có n nút giao thông và m con đường hai chiều
nối một số nút giao thông. Chiều dài của mỗi con đường được tính bằng một số nguyên dương (mét);
những con đường này có thể có độ dài khác nhau.
3
Hôm nay, Nam dự định sẽ đi thăm một trong những địa điểm nổi tiếng của NewYork, đó là công
viên trung tâm Center Park bằng taxi.
Ban đầu, mỗi nút giao thông có đúng một xe taxi đang chờ tại đó. Người lái xe taxi tại nút thứ i
đồng ý chở Nam (có thể qua một số nút giao thông trung gian) đến một nút giao thông khác nếu khoảng
cách đi không quá ti (mét). Ngoài ra, cước phí đi chiếc taxi này không phụ thuộc vào khoảng cách đi mà
được tính bằng ci (dollar). Taxi không thể dừng lại ở giữa đường. Mỗi xe taxi chỉ được sử dụng không
quá một lần.
Lúc ban đầu, Nam chỉ có thể đón taxi ở nút giao thông x, nơi cậu ta xuất phát. Công viên trung tâm
Center Park ở nút giao thông y.
Yêu cầu: Hãy xác định số tiền tối thiểu Nam cần phải trả cước taxi để đến được Center Park, hoặc
cho biết điều đó là không thể.

Input

 Dòng đầu chứa hai số nguyên n và m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000) cách nhau bởi dấu cách, tương
ứng là số nút giao thông và số con đường hai chiều. Các nút được đánh số từ 1 đến n.
 Dòng tiếp theo chứa hai số nguyên x và y cách nhau bởi dấu cách (1 ≤ x, y ≤ n), tương ứng là nút
giao thông nơi Nam bắt đầu chuyến đi và nút giao thông nơi có Center Park.
 Dòng thứ i trong m dòng tiếp theo chứa 3 số nguyên cách nhau bởi dấu cách ui, vi , wi, cho biết con
đường hai chiều thứ i nối trực tiếp hai nút giao thông ui và vi có độ dài wi (1 ≤ ui  vi ≤ n, 1 ≤ wi ≤
109
). Chú ý, giữa hai nút giao thông bất kỳ có thể có hơn một con đường nối trực tiếp.
 Dòng thứ j trong n dòng tiếp theo chứa cặp số nguyên cách nhau bởi dấu cách tj và cj (1 ≤ tj, cj ≤
109
), cho biết xe taxi đang đỗ ở nút giao thông thứ j có thể đi khoảng cách tối đa là tj và cước phí
mà xe đó đòi chi trả là cj.

Output

Nếu Nam không thể đến được Center Park bằng hệ thống taxi nói trên thì in ra số -1.
Ngược lại thì in ra tổng cước phí tối thiểu mà Nam phải trả.

Scoring

Có 60