| 问题描述 |
|---|
小易有张藏宝图，这张地图上标记了起点、终点以及三处宝藏的位置。 这张藏宝图可以看成是有$$n$$个点，$$m$$条边的无向带权连通图，边权即为该路径的距离。 其中出发点的编号是$$1$$，终点的编号是$$n$$，三个宝藏的位置编号分别是$$x,y,z$$。 求小易最少需要走多少的总距离，才可以使得他收集完全部宝藏后，从终点离开。 注：只要经过宝藏所在地即为收集完成，经过终点时可以选择不离开，继续收集。
|
| 输入描述 |
第一行是一个正整数$$T$$表示测试案例的数量。（$$1 \le T \le 10$$） 每组案例先输入$$n,m,x,y,z$$含义见描述。（$$1\le n \le 50000$$，$$n-1 \le m \le 50000$$） 接下来$$m$$行，每行输入三个正整数$$u,v,w$$，表示顶点$$u$$和$$v$$之间有一条权为$$w$$的无向边。（$$1 \le w \le 10^9$$） 数据量较大，请使用快速的输入输出方式。
|
| 输出描述 |
针对每组样例，输出一个整数，表示从起点出发，集齐三个宝藏后，再从终点离开最少需要花费的时间，然后换行。 |
| 样例输入复制样例 |
1 5 4 2 3 4 2 1 1 1 4 1 4 5 1 5 3 1 |
| 样例输出 |
6 |
| 提示说明 |
题目来源：JMU第八届天梯校选 |
| 相关 |