Bóng Chuyền

Một thành phố có $n$ ngã tư, được đánh số từ $1$ đến $n$. Một số cặp ngã tư được nối với nhau bằng các con đường hai chiều có độ dài nguyên dương. Giữa một cặp ngã tư có thể có nhiều con đường khác nhau.

Tại ngã tư thứ $i$ có duy nhất một chiếc taxi. Người lái taxi này đồng ý chở khách (có thể đi qua nhiều ngã tư trung gian) đến một ngã tư khác bất kỳ với điều kiện tổng quãng đường di chuyển không vượt quá $t_i$ mét. Chi phí một chuyến đi bằng taxi tại ngã tư $i$ luôn cố định là $c_i$ đồng, không phụ thuộc vào quãng đường. Mỗi chiếc taxi chỉ được sử dụng nhiều nhất một lần, và khách chỉ có thể bắt taxi tại ngã tư nơi nó đứng.

Bạn đang ở ngã tư $x$ và cần đến ngã tư $y$. Hãy tìm tổng chi phí nhỏ nhất để đi từ $x$ đến $y$.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên $n$ và $m$ — số ngã tư và số con đường.
• Dòng thứ hai chứa hai số nguyên $x$ và $y$ — ngã tư xuất phát và ngã tư đích.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u_i$, $v_i$, $w_i$ — mô tả con đường nối ngã tư $u_i$ và $v_i$ có độ dài $w_i$.
• $n$ dòng cuối, dòng thứ $i$ chứa hai số nguyên $t_i$ và $c_i$ — quãng đường tối đa và chi phí của taxi tại ngã tư $i$.

Dữ liệu ra

In ra tổng chi phí nhỏ nhất để đi từ $x$ đến $y$. Nếu không thể đi đến được, in ra $-1$.

Ràng buộc

• $1\le n\le 1000$
• $0\le m\le 1000$
• $1\le x,y\le n$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $1\le w_i\le {10}^9$
• $1\le t_i,c_i\le {10}^9$

Ví dụ