Dear Viewer,

Here is the synopsis of the new episode of Steiner's Gate that you have requested from MyAlgorithmList (MAL).

Okabe is exploring the 'tree' of time. He has mapped out how different timelines are connected and the cost of jumping between them. He has identified 3 critical timelines that he must be able to reach.

He remembers these words: Time is passing so quickly. Right now, I feel like complaining to Einstein. Whether time is slow or fast depends on perception. Relativity theory is so romantic. And so sad.

Okabe needs to find the minimum cost to establish a network of jumps from the 'tree' of time that connects all 3 critical timelines. He can choose any subset of the available jumps to build this network, and the total cost is the sum of all chosen jump costs. The network must allow Okabe to travel between any of the 3 critical timelines (possibly through intermediate timelines).

Input Format

The first line contains two integers n and e, where n is the number of timelines and e is the number of possible jumps. Timelines are numbered from 1 to n.

The next e lines each contain three integers i j k, representing a bidirectional jump between timeline i and timeline j with cost k.

The final line contains three integers representing the 3 critical timelines that must be connected.

It is guaranteed that all timelines will be connected by some sequence of jumps.

Output

Return the minimum cost of a network of jumps that connects the 3 critical timelines.

Sample Input 1

4 3
1 4 5
4 2 7
4 3 12
1 2 3

Sample Output 1

24