暂无测试数据。

$\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$