暂无测试数据。

\(\Large\texttt{此题未完结，大概要咕(unsigned \_\_int128)(-1)天}\)
yinjun看到了OIer们的温馨，决定免费提供数据！<——？？？

题目背景

\(12:00\)，下课了。

\(Did\ \)交给了你一个任务——护送\(\ yinjun\ \)到食堂吃饭。

不幸的是，由于\(\ yinjun\ \)太太太太太太太太太太太太太太太太太太太可爱了，他和你走散了。

题目描述

你们身处在一个特殊的学校，这个学校的形状可近似看为有 \(n\) 个点， \(m\) 条边的一张图，道路是双向的，你和 \(yinjun\) 分别在这个图的点 \(a,b\) 上，食堂在点 \(k\) 。

现在，你需要和他到某个点汇合后一起前往食堂（此点不能为食堂）。

你想知道，你们两个人需要走的路程总和最少为多少。

输入格式

第一行两个数 \(n,m\) ,表示总点数和边数。

接下来 \(m\) 行每行有三个数 \(a,b,c\) ，表示 \(a\) 和 \(b\) 间有一条长 \(c\) 的边。

最后一行三个数 \(x,y,k\) ，其中 \(x\) 和 \(y\) 分别表示你和 \(yinjun\) 所在的点， \(k\) 表示食堂所在的点。

输出格式

输出一行一个数，为你们两人所走路程之和的最小值。

样例

输入

5 4
1 2 3
2 3 4
3 4 5
4 5 6
1 5 2

输出

18

提示说明

对于 \(30\%\) 的数据， \(n\le10\) 。

对于另外 \(10\%\) 的数据，图是一条链。

对于另外 \(20\%\) 的数据，图是一个环。

对于 \(100\%\) 的数据，\(1\le n\le 10^3\) , \(1\le m\le 10^4\) , \(1\le a,b\le n\) , \(1\le c\le 10\) ,\(1\le x,y,k\le n\) ，保证图联通

来源： \(mazihang2022\)