Description

Recently, Elaxia and w** have become very close. They want to be together all day, but university studies are intense, so they must plan their time together wisely.

Elaxia and w** commute daily between their dormitories and laboratories. They hope to maximize the time they walk together while still minimizing their own travel time.

You are given the IDs of Elaxia's dormitory and laboratory and w**'s dormitory and laboratory, as well as the school map: the map has $n$ intersections and $m$ roads, and traversing each road takes a certain amount of time. Specifically, on an undirected graph, find the longest common path shared by the shortest paths between two pairs of vertices.

Input Format

The first line contains two positive integers $n,m$, the numbers of vertices and edges.

The second line contains four positive integers $x_1,y_1,x_2,y_2$, which are the IDs of Elaxia's dormitory and laboratory, and w**'s dormitory and laboratory, respectively.

Each of the next $m$ lines contains three integers $u,v,w$, meaning there is an edge between $u$ and $v$, and it takes $w$ time to traverse.

Output Format

Output a single integer, the length of the longest common path.

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

3

Hint

Constraints
For $30\%$ of the testdata, $1\le n \le 100$.
For $60\%$ of the testdata, $1\le n \le 1000$.
For $100\%$ of the testdata, $1\le n \le 1500$, $1 \leq m \leq 3 \times 10^5$, $1\le w \le 10^4$. The input guarantees there are no multiple edges or self-loops.

Translated by ChatGPT 5