题目描述

光头强要在城市中租房子，他想要找到一处合适的住址，使得到商场、工作地点、医院的距离和最小。城市可以抽象为一张简单无向图，边权都为非负整数。

图用以下形式给出：

第一行输入两个整数 $n,m$，表示图的顶点数和边数，顶点编号从 1 到 $n$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x,y$ 之间有一条边，边权为 $z$。

接下来一行三个整数 $a,b,c$, 分别表示商场、工作地点、医院所在的顶点的编号。

你需要寻找一个合适的居住点（这个点可以和 $a,b,c$ 重合），并输出最小的距离和。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，每行有三个整数，代表一条边。

接下来一行三个整数 $a,b,c$。

输出格式

输出一个数表示答案。

4 3
1 2 1
2 3 1
3 4 1
1 2 4

3

数据规模

对于所有数据，保证 $3≤n≤5000,0≤m≤10000,1≤x,y,a,b,c≤n,x≠y,1≤z≤10000, a,b,c$ 两两不同，数据保证整张图连通。