Lan và Kiều cùng sống trong một thành phố, thành phố này có $n$ giao lộ được đánh số từ $1$ đến $n$, và có $m$ con đường hai chiều được đánh số từ $1$ đến $m$. Mỗi con đường có một thời gian di chuyển.

Lan và Kiều có lịch trình riêng của mình, họ xuất phát từ điểm xuất phát của mỗi người, đi qua một số giao lộ, cuối cùng đến đích của riêng mình.

Tuy nhiên, trước khi đến đích, họ cần gặp nhau tại một giao lộ nào đó.

Họ xuất phát cùng một thời điểm, mục tiêu là tìm một điểm gặp nhau sao cho thời gian đến của người đến điểm gặp muộn nhất là nhỏ nhất. Tương tự, họ cũng mong muốn trong các thời gian đi từ điểm gặp đến đích của mỗi người, thời gian đến của người đến muộn nhất cũng là nhỏ nhất.

Nhiệm vụ của bạn là giúp họ tìm một giao lộ để gặp nhau, tìm tổng thời-gian-đến-muộn-nhất sớm nhất từ điểm xuất phát đến điểm gặp rồi từ điểm gặp đến đích của mỗi người, và in ra thời gian này; nếu không tồn tại phương án hợp lệ thì in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$, biểu thị số giao lộ và số con đường trong thành phố.

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$ và $t_i$, biểu thị giữa giao lộ $a_i$ và giao lộ $b_i$ có một con đường hai chiều với thời gian di chuyển là $t_i$.

Dòng tiếp theo chứa bốn số nguyên $s_1$, $e_1$, $s_2$, $e_2$, biểu thị Lan xuất phát từ $s_1$ đi đến $e_1$, còn Kiều xuất phát từ $s_2$ đi đến $e_2$.

Dữ liệu ra

In ra một dòng chứa một số nguyên, biểu thị tổng thời gian của các đường đi có thời gian ngắn nhất từ điểm xuất phát của mỗi người đến điểm gặp rồi đến đích; nếu không tồn tại phương án hợp lệ thì in ra $-1$.

Ví dụ

Input

4 4
1 2 1
2 3 2
3 4 3
4 1 1
1 4 2 3

Output

3

Ghi chú

Phạm vi dữ liệu

Với mọi dữ liệu thử nghiệm, thỏa mãn:

• $2 \le n \le 100$

• $n-1 \le m \le \dfrac{n(n-1)}{2}$

• $1 \le a_i,b_i,s_i,e_i \le n$

• $a_i \neq b_i$, $s_i \neq e_i$

• $1 \le t_i \le 100$