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