时间限制：1秒　　内存限制：256M

---

【问题描述】

　　在 \(N\) 个点 \(M\) 条无向边的图中（点用 \(1..N\) 编号），给定 \((s_1,e_1)、(s_2,e_2)\)，请编程计算 \(s_1\) 与 \(e_1\) 之间和 \(s_2\) 与 \(e_2\) 之间两条最短路径的最长公共路径。

【输入格式】

　　输入的第一行为 \(N\) 和 \(M\) 。第二行为四个整数：\(s_1,e_1,s_2,e_2\)，其中 \(s_1,e_1\) 是一条最短路的两个端点，\(s_2,e_2\) 是另一条最短路的两个端点。接下来 \(M\) 行，每行包含三个整数 \(u,v,len\)，表示路口 \(u\) 和 \(v\) 之间有一条双向边，长度为 \(len\)。

【输出格式】

　　输出一个整数，表示最长公共路径的长度。

【输入输出样例】

　Input

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

　Output

3

【样例解释】

　　样例图形如下：

　　\(s_1\) 与 \(e_1\) 之间的一条最短路径：1—3—5—7—2
　　\(s_2\) 与 \(e_2\) 之间的一条最短路径：2—7—5—3—6
　　公共路径为：3—5—7，长度为4。

【数据限制】

　　对于 \(30\%\) 的数据，\(1<=n<=100\)
　　对于 \(60%\$ 的数据，\)1<=n<=1000\(
　　对于 100\%\) 的数据，\(1<=n<=1500，1<=m<=300000 ，0<t<=10000\) 输入数据保证没有自环。

【来源】

　　Mr.he