Có ~N~ trung tâm điều phối. Trung tâm ~i~ có tọa độ ~\left(x_i, y_i\right)~ trên mặt phẳng.

Giữa một số cặp trung tâm có các tuyến đường bộ hai chiều. Ngoài ra, có thể bay trực tiếp bằng drone giữa bất kỳ hai trung tâm nào.

• Nếu đi bằng đường bộ giữa hai trung tâm được nối trực tiếp, chi phí là trọng số của cạnh đó.
• Nếu bay drone trực tiếp từ trung tâm ~u~ đến trung tâm ~v~, chi phí là khoảng cách Manhattan:

~|x_u - x_v| + |y_u - y_v|~.

Yêu cầu

Tìm chi phí nhỏ nhất để đi từ trung tâm ~S~ đến trung tâm ~T~.

Dữ liệu

• Dòng ~1~ chứa bốn số nguyên ~N, M, S, T~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, y_i~ là tọa độ của trung tâm ~i~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, w~, mô tả một tuyến đường bộ hai chiều giữa ~u~ và ~v~ có chi phí ~w~.

Kết quả

In ra một số nguyên duy nhất là chi phí nhỏ nhất để đi từ ~S~ đến ~T~.

Ví dụ

Ví dụ 1

Input

4 2 1 4
0 0
2 1
1 2
3 0
1 2 10
3 4 8

Output

3

Giải thích

Ví dụ 1

Chi phí bay drone trực tiếp từ ~1~ đến ~4~ là:

~|0-3| + |0-0| = 3~.

Đây là lộ trình tối ưu.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^3~.
• ~1 \le M \le 10^3~.
• ~1 \le S, T \le N~.
• ~-10^3 \le x_i, y_i \le 10^3~.
• ~1 \le u, v \le N~.
• ~1 \le w \le 10^4~.

Chấm điểm

• Subtask ~1~: ~40\%~ số điểm, ~N \le 20~, ~M \le 100~.
• Subtask ~2~: ~60\%~ số điểm, không có ràng buộc bổ sung.