P3003 [USACO10DEC] Apple Delivery S

题目描述

Bessie 有两只鲜红的苹果要送给她在牛群中的两个朋友。

她要走 $C$ 条牛道（$1 \le C \le 2 \times 10^5$），这些牛道构成了一个常见的图，方便地连接了 $P$ 个牧场（$1 \le P \le 10^5$），这些牧场的编号从 $1$ 到 $P$：没有牛道从一个牧场通向自身，牛道是双向的，每条牛道都有一个相关的距离，最重要的是，总是可以从任何一个牧场到达另一个牧场。

每条牛道连接两个不同的牧场 $P1_i$（$1 \le P1_i \le P$）和 $P2_i$（$1 \le P2_i \le P$），它们之间的距离为 $D_i$。所有距离 $D_i$ 的总和不超过 $2 \times 10^9$。

Bessie 要从牧场 $PB$（$1 \le PB \le P$）出发，按任意顺序访问牧场 $PA_1$（$1 \le PA_1 \le P$）和 $PA_2$，送完两个苹果后，求她必须行走的最小总距离。当然，这三个牧场是不同的。

输入格式

第一行包含五个用空格分隔的整数：$C, P, PB, PA_1$ 和 $PA_2$。

第 $2$ 行到第 $C+1$ 行：第 $i+1$ 行描述牛道 $i$，给出它连接的两个牧场及其之间的距离：$P1_i, P2_i, D_i$。

输出格式

一行一个整数：Bessie 必须行走的最短距离。

样例输入

9 7 5 1 4
5 1 7
6 7 2
4 7 2
5 6 1
5 2 4
4 3 2
1 2 3
3 2 2
2 6 3

样例输出

12

样例说明

样例中 Bessie 从牧场 $5$ 出发，要把苹果送到牧场 $1$ 和牧场 $4$。最佳路线是：

$5 \to 6 \to 7 \to 4 \to 3 \to 2 \to 1$，总距离为 $1 + 2 + 2 + 2 + 2 + 3 = 12$。