/ GMQ OJ / 题库 /

『yinjun』护送行动(未完成)

『yinjun』护送行动(未完成)

暂无测试数据。

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

题目背景

12:0012:00,下课了。

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

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

题目描述

你们身处在一个特殊的学校,这个学校的形状可近似看为有 nn 个点, mm 条边的一张图,道路是双向的,你和 yinjunyinjun 分别在这个图的点 a,ba,b 上,食堂在点 kk

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

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

输入格式

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

接下来 mm 行每行有三个数 a,b,ca,b,c ,表示 aabb 间有一条长 cc 的边。

最后一行三个数 x,y,kx,y,k ,其中 xxyy 分别表示你和 yinjunyinjun 所在的点, kk 表示食堂所在的点。

输出格式

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

样例

输入

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

输出

18

提示说明

对于 30%30\% 的数据, n10n\le10

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

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

对于 100%100\% 的数据,1n1031\le n\le 10^3 , 1m1041\le m\le 10^4 , 1a,bn1\le a,b\le n , 1c101\le c\le 10 ,1x,y,kn1\le x,y,k\le n ,保证图联通

来源: mazihang2022mazihang2022

信息

ID
1035
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者