Tối nay, Luna được mời đến một bữa tiệc tại nhà một người bạn. Sau một ngày dài, anh chỉ muốn nhanh chóng đến nơi, thưởng thức những món ăn ngon và trò chuyện cùng mọi người. Tuy nhiên, nhìn xuống những con đường đông đúc bên dưới, Luna lập tức từ bỏ ý định xuống phố để đi bộ sang đó.

May mắn thay, Luna đang ở trong một khu đô thị đặc biệt. Khu đô thị gồm ~n~ tòa nhà, được đánh số từ ~1~ đến ~n~, nối với nhau bằng ~m~ cây cầu trên không. Nhờ những cây cầu này, cư dân có thể đi từ tòa nhà này sang tòa nhà khác mà không cần bước xuống đường phố.

Mỗi cây cầu nằm tại một tầng nhất định. Cụ thể, cây cầu thứ ~i~ nối tầng ~c_i~ của tòa nhà ~u_i~ với tầng ~c_i~ của tòa nhà ~v_i~ và cho phép di chuyển theo cả hai chiều. Để sử dụng cây cầu, Luna phải đến đúng tầng ~c_i~ tại một trong hai tòa nhà. Sau khi đi qua cầu, anh sẽ ở tầng ~c_i~ của tòa nhà còn lại. Có thể có nhiều cây cầu nối cùng một cặp tòa nhà, kể cả tại cùng một tầng.

Bên trong mỗi tòa nhà đều có thang máy phục vụ tất cả các tầng. Việc đi từ tầng ~x~ đến tầng ~y~ mất ~|x-y|~ đơn vị thời gian, bất kể đi lên hay đi xuống. Luna không phải chờ thang máy; thời gian ra vào thang máy và đi qua cầu đều được xem là không đáng kể.

Hiện tại, Luna đang ở tầng ~h_s~ của tòa nhà ~s~, còn bữa tiệc được tổ chức tại tầng ~h_t~ của tòa nhà ~t~. Anh quyết định chỉ sử dụng thang máy và các cây cầu để đến bữa tiệc, tuyệt đối không di chuyển giữa các tòa nhà bằng đường phố.

Hãy giúp Luna tìm thời gian nhỏ nhất để đến đúng tầng tổ chức bữa tiệc.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~, (~2 \le n \le 2\cdot 10^5, n - 1 \le m \le 2 \cdot 10^5~).

Dòng thứ hai chứa bốn số nguyên ~s, t, h_s, h_t~, (~1 \le s, t \le n, 1 \le h_s, h_t \le 10^9~).

~m~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u_i, v_i, c_i~, (~1 \le u_i, v_i \le n, 1 \le c_i \le 10^9~).

Mạng lưới các tòa nhà đảm bảo liên thông.

Output

In ra một số nguyên duy nhất - thời gian nhỏ nhất để Luna đến được tầng ~h_t~ của tòa nhà ~t~.

Sample Input

4 4 
1 4 2 8 
1 2 5 
2 4 9 
1 3 3 
3 4 7

Sample Output

6