Bessie's Apple Delivery

Bessie has two crisp red apples that she must deliver to two of her friends. She is currently located at pasture \(P_B\) and her two delivery destinations are pastures \(P_{A1}\) and \(P_{A2}\). The farm consists of \(P\) pastures (numbered 1 through \(P\)) connected by \(C\) bidirectional cowpaths. Each cowpath connects two distinct pastures and has an associated positive distance \(D_i\). It is guaranteed that there is a path between any two pastures and the sum of all distances does not exceed \(2\times10^9\).

Your task is to compute the minimum total distance Bessie must travel in order to start at pasture \(P_B\) and deliver both apples (by visiting both \(P_{A1}\) and \(P_{A2}\) in any order). In other words, the answer is the smaller of the two routes:

[ d(P_B, P_{A1}) + d(P_{A1}, P_{A2}) \quad \text{or} \quad d(P_B, P_{A2}) + d(P_{A1}, P_{A2}), ]

where \(d(u,v)\) denotes the shortest-path distance between pastures \(u\) and \(v\). Note that since the graph is undirected and the distances satisfy the triangle inequality, this approach yields the correct answer.

Example:

Input:
7 9 5 1 4
1 2 3
2 3 2
3 4 2
1 5 7
2 5 4
2 6 3
5 6 1
7 4 2
6 7 2
Output:
12

In the above example, Bessie starts at pasture 5 and delivers the apples to pastures 1 and 4. The optimal route is:

5 -> 6 -> 7 -> 4 -> 3 -> 2 -> 1

with a total distance of 12.

inputFormat

The input begins with a single line containing five integers: \(P\), \(C\), \(P_B\), \(P_{A1}\), and \(P_{A2}\), where \(1 \le P \le 10^5\) and \(1 \le C \le 2\times10^5\). Each of the next \(C\) lines contains three integers \(P_{1_i}\), \(P_{2_i}\), and \(D_i\) (with \(1 \le P_{1_i},P_{2_i} \le P\) and \(P_{1_i} \neq P_{2_i}\)) representing a cowpath between two pastures and its distance. It is guaranteed that any pasture is reachable from any other pasture and that the sum of all \(D_i\) does not exceed \(2\times10^9\>.

outputFormat

Output a single integer representing the minimum total distance required for Bessie to deliver both apples.

sample

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

12