Optimized Commuter Pass

JOI-kun lives in a city with \(N\) stations numbered from \(1\) to \(N\) and \(M\) bidirectional railways. The \(i\)th railway (\(1 \le i \le M\)) connects stations \(A_i\) and \(B_i\) with a fare of \(C_i\) yen. JOI-kun lives near station \(S\) and attends IOI High School near station \(T\). He must purchase a commuting pass which allows him to travel (in either direction) on a fixed set of railways without additional cost. When purchasing the pass, he must choose a route from \(S\) to \(T\) which has the minimum total cost (i.e. a shortest path in terms of total fare).

In addition, JOI-kun frequently visits a bookstore near station \(U\) and station \(V\). When traveling from \(U\) to \(V\), he pays:

• \(0\) yen for any railway that is part of the commuting pass (i.e. the chosen \(S\)–\(T\) route), and
• \(C_i\) yen for any railway that is not part of the commuting pass.

The total fare from \(U\) to \(V\) is the sum of the fares for the individual railways used during the trip. JOI-kun wants to know the minimum possible cost from \(U\) to \(V\) if he chooses the commuting pass (i.e. the \(S\)–\(T\) route) optimally among all shortest paths. Note that he may also choose to not use any free segment provided by the pass if that is optimal.

Task: Given the city information and the four stations \(S\), \(T\), \(U\), and \(V\), determine the minimum cost JOI-kun must pay when traveling from \(U\) to \(V\) after purchasing an optimally chosen commuting pass.

Hint: Let the original graph have edge weights \(C_i\). Denote \(d(X,Y)\) as the minimum cost of traveling between stations \(X\) and \(Y\) using the original fares. Then, if JOI-kun does not use the commuting pass for any part of his journey, his cost is \(d(U,V)\). Otherwise, he may choose two stations \(X\) and \(Y\) that lie on a common \(S\)–\(T\) shortest path satisfying \[ d(S,X) + d(X,Y) + d(Y,T) = d(S,T), \] where \(d(S,T)\) is the cost of the \(S\)–\(T\) shortest path. By boarding the free (commuting pass) segment at \(X\) and leaving at \(Y\), his cost becomes \[ d(U,X) + d(Y,V). \] The answer is the minimum of \(d(U,V)\) and \(d(U,X) + d(Y,V)\) over all valid \(X, Y\) pairs.

inputFormat

The input is given in the following format:

N M
A1 B1 C1
A2 B2 C2
⋮
AM BM CM
S T U V

Where:

• \(1 \leq N \leq 200\) is the number of stations.
• \(1 \leq M \leq 1000\) is the number of railways.
• For each \(i\), \(1 \leq A_i, B_i \leq N\) and \(1 \leq C_i \leq 10^4\).
• \(S\), \(T\), \(U\), and \(V\) are station numbers.

outputFormat

Output the minimum cost from station \(U\) to station \(V\) as an integer.

sample

4 4
1 2 3
2 3 4
3 4 5
1 4 15
1 4 2 3

0