Cho một đồ thị vô hướng, liên thông gồm ~n~ đỉnh được đánh số từ ~1~ đến ~n~ và ~m~ cạnh được đánh số từ ~1~ đến ~m~. Cạnh thứ ~i~ nối đỉnh ~u_{i}~ với đỉnh ~v_{i}~ và có trọng số ~w_{i}~ mỗi cạnh của đồ thị ta có thể tăng thêm một đại lượng nguyên không âm để trọng số của cạnh đó là một số nguyên tố.

Yêu cầu

Hãy tìm một đường đi từ đỉnh ~s~ đến đỉnh ~t~ chỉ đi qua các cạnh có trọng số là số nguyên tố (sau khi đã tăng) với tổng giá trị tăng của các cạnh là nhỏ nhất có thể.

Dữ liệu đầu vào

Gồm ~m + 1~ dòng:

• Dòng thứ nhất gồm bốn số nguyên dương ~n, m, s, t~ ~(n, m \le 10^5;\ s, t \le n)~.
• Dòng thứ ~i~ trong ~m~ dòng sau chứa ba số nguyên dương ~u_i, v_i, w_i~ ~(1 \le u_i, v_i \le n;\ w_i \le 10^6)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là tổng giá trị tăng nhỏ nhất của các cạnh tìm được.

Ràng buộc dữ liệu

• Có 20% số test tương ứng với 20% số điểm của bài có ~u_i + 1 = v_i\ \forall i = 1..m~.
• Có 40% số test tương ứng với 40% số điểm của bài có ~n, m \le 2000~.
• Có 40% số test tương ứng với 40% số điểm của bài có ~2000 < n, m \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

4 5 1 4
1 2 20
1 3 3
2 4 10
3 4 6
1 4 15

OUTPUT

1

Giải thích: