European Rover Challenge!

The European Rover Challenge (ERC) Space and Robotics Event is a prestigious space-robotics event combining international competitions of mobile robots with scientific and technological shows. University teams from around the world build their own Martian robots, and then take part in competitions similar to the tasks performed by rovers on the surfaces of Mars and the Moon. This year your university team has been selected to participate and you are the chief programmer of your team.

This year, the task of the competition is to collect valuable samples from the surface of Mars. Of course, it is a simulation area designed for the competition and the specifics are as follows:

1. The planet Mars has been divided into certain Areas of Interest (AoI) where the valuable samples may be present. There are three possible samples: a rock sample, a water sample, and a micro-organism sample.
2. The rover robot of your team must travel to these AoIs and collect all the samples as they are essential to determine whether life is sustainable in Mars.
3. The distances between the AoIs and the location of the samples will be known beforehand. There maybe multiple roads between two AoIs but no road connects the same AoI with itself (What's the point, right?).
4. The battery life of your rover robot is limited and the samples must be collected using minimum energy.
5. The distance travelled by the robot is directly proportional to the battery life consumed.
6. The robot will always start from a specific location and will have to carry all the samples to the retrieval AoI to end the competition.

Given the input parameters of the simulation area, find the minimum distance covered as output. Assume that it is always possible to carry all the samples to the retrieval location.

Input

There maybe $T$ ($1 \leq T \leq 10$) simulations in the competition and you have to complete all of them.

Each simulation starts with six integers: $N$ ($1 \leq N \leq 100000$), the number of AoIs, $M$ ($0 \leq M \leq 100000$) - the number of roads connecting the AoIs, $a$, $b$, $c$ ($1 \leq a, b, c \leq N$), the three sample locations and, $r$ ($1 \leq r \leq N$), the retrieval location.

The next $M$ lines each contain three road parameters: $u$, $v$, $w$ ($1 \leq u, v, w \leq 100000$), where $u$ and $v$ are the connecting ends of the roads and, $w$ is the distance between the end AoIs. The starting location is always '1'.

Subtasks

• Subtask 1 (40 points): The roads connecting the AoIs have identical distances.
• Subtask 2 (60 points): The roads connecting the AoIs have variable distances.

Output

Output only one integer for every simulation: the distance travelled by the robot while collecting all the samples and returning to the retrieval location using minimum battery energy.

Samples

Input	Output
1 6 6 3 5 4 6 1 2 1 2 3 1 2 5 1 5 4 1 2 4 1 4 6 1	6

Input	Output
2 10 11 5 2 7 10 1 2 1 1 3 2 2 3 5 3 5 1 3 4 2 5 4 2 4 6 5 6 7 6 6 8 1 8 10 3 8 9 3 10 15 5 7 9 10 1 2 1 1 3 2 2 3 5 4 7 4 3 5 1 3 4 2 2 6 2 5 4 2 4 6 5 6 7 6 6 8 1 7 9 1 8 10 3 8 9 3 6 10 7	28 16

Dataset can be large, use fast I/O methods.