Recently, Elaxia and w have become very close and want to spend as much time together as possible. However, their university studies are very demanding, so they must arrange their time together reasonably. Every day, Elaxia and w travel between their dormitories and laboratories. They want to maximize the time they spend walking together while minimizing their total travel time.

The school map is given as an undirected graph with $N$ intersections and $M$ roads, where each road takes a certain amount of time to traverse. Specifically, you are asked to find the length of the longest common path between the shortest paths of two pairs of nodes in the undirected graph.

Input

The first line contains two integers $N$ and $M$ (as described above).

The second line contains four integers $x_1, y_1, x_2, y_2$ ($1 \leq x_1, y_1, x_2, y_2 \leq N$), representing the dormitory and laboratory indices for Elaxia and w**, respectively (the two pairs of points are $x_1, y_1$ and $x_2, y_2$).

The next $M$ lines each contain three integers $u, v, l$ ($1 \leq u \leq N, 1 \leq v \leq N, 1 \leq l \leq 10\,000$), representing a road between $u$ and $v$ with a travel time of $l$.

Output

A single integer representing the maximum time the two can spend together (i.e., the length of the longest common path).

Examples

Input 1

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

Output 1

3

Subtasks

• For $30\%$ of the data, $N \leq 100$.
• For $60\%$ of the data, $N \leq 1\,000$.
• For $100\%$ of the data, $N \leq 1\,500$. The input is guaranteed to have no multiple edges or self-loops.