时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
在人类看不到的地方，蚂蚁正悄悄建立着自己的地下王国。地下王国是由n个洞穴m条边组成的，这n个洞穴用1到n标号，第i条边连接洞穴ui和洞穴vi，长度为wi。（可以将其看做是n个点m条边的无向图）
在地下王国里，蚂蚁们最喜欢参加一些聚会活动。假如有一只蚂蚁（我们称为蚂蚁A）准备去洞穴T1聚会，它最好的朋友（我们称为蚂蚁B）准备去洞穴T2聚会，它们同时出发，蚂蚁A和蚂蚁B都很聪明，会走最短的路线到达目的地。然而这两只蚂蚁注意到它们各自选择的路径可能有公共路径，它们在公共路径上能边走边聊，于是这两只蚂蚁想尽量找到最长的公共路径。你能帮帮它们吗？
输入描述:
第一行：两个整数N和M（含义如题目描述）。
第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ y2 ≤ N），分别表示蚂蚁A所在洞穴的标号，蚂蚁A要去的洞穴标号，蚂蚁B所在洞穴的标号，蚂蚁B要去的洞穴标号（两对点分别 x1,y1和x2,y2）。
（输入数据保证这四点互不相同）
接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表示洞穴u和洞穴v之间有一条路，这条路的长度为l。
输出描述:
一行，一个整数，即最长公共路径的长度。
示例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
备注:
N ≤ 1500，M ≤ 300000，输入数据保证没有重边和自环。