新年好

题目描述

重庆有 $n$ 个车站和 $m$ 条双向公路。任意两站之间最多有一条公路，且整个路网连通。每条公路有一个通行时间。佳佳住在车站 $1$，他的五位亲戚分别住在 $a,b,c,d,e$。求从家出发、以任意顺序拜访全部五位亲戚的最少总时间。拜访结束后不要求返回家中。

输入格式

第一行输入 $n,m$。第二行输入 $a,b,c,d,e$。接下来 $m$ 行，每行输入 $x,y,t$，表示连接 $x,y$ 的双向公路耗时 $t$。

输出格式

输出最少总时间。

6 6
2 3 4 5 6
1 2 8
2 3 3
3 4 4
4 5 5
5 6 2
1 6 7

21

说明与数据范围

$1\le n\le50000$，$1\le m\le100000$，$1<a,b,c,d,e\le n$，$1\le x,y\le n$，$1\le t\le100$。原题来自 CQOI 2005。

来源

ybt1500