【题目背景】

这是一个 $N$ 个城市 $M$ 条无向道路的国家。

这个国家有两个骑士，他们关系很好，现在他们分别被要求沿最短路从 $X1$ 走到 $Y1$ ，从 $X2$ 走到 $Y2$ ，他们希望两条路径的公共部分最长。

【输入格式】

第一行两个数 $N,M$ 表示城市数和道路数。

第二行四个数 $X1,Y1,X2,Y2$，意义如上所述。

接下来 $M$ 行，每行 $3$ 个数 $A,B,C$ 表示 $A,B$ 间有一条长度为 $C$ 的路。

【输出格式】

输出 $X1$ 到 $Y1$ ，$X2$ 到 $Y2$ 的最短路的公共部分最长。

【样例 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

3

【数据范围】

对于 $30\%$ 的数据，$N ≤ 100$；

对于 $60\%$ 的数据，$N ≤ 1000$；

对于 $100\%$ 的数据，$N ≤ 1500$，$M <= 3000，1 <= A,B <= N, 1 <= C <= 10000$，输入数据保证没有重边和自环。