The Chamber's Secrets

In the secret chamber, there are n small rooms numbered from \(1,2,...,n\).

There are \(m\) bidirectional corridors connecting pairs of distinct rooms; each corridor connecting two rooms \(u\) and \(v\) takes \(C_i\) time to traverse. No two rooms have more than one corridor between them.

Both Harry and Ron start at room 1. They have two distinct objectives: to rescue Ginny and to find the diary, located in two different rooms \(a\) and \(b\) respectively. They want to minimize the overall time needed to reach both target rooms. The two can split up and travel concurrently if possible.

However, some rooms are special: only someone who can speak with snakes (i.e. only Harry) is allowed to enter these restricted rooms. Ron cannot enter these rooms. Note that room 1 is always accessible to both.

Your task is to compute the minimum overall time needed for them to cover the two target rooms. In other words, if both travel simultaneously then the finish time is the maximum of the individual arrival times. Moreover, if a target room is restricted then only Harry can go to that room. If both target rooms are restricted, then only Harry can visit both targets sequentially. It is allowed that if one target is unreachable by Ron due to restrictions then Harry can cover both targets (in the best order).

Input constraints and details:

• When both targets are accessible to Ron (i.e. non‐restricted), you may assign one target to Ron and the other to Harry, taking the minimum of the possible assignments.
• If one of the targets is restricted, then that target must be visited by Harry and the other by Ron if possible; otherwise, Harry must visit both.
• If both targets are restricted then Harry must plan a route starting from room 1 that visits both targets (in the optimal order).

All corridors exist in a connected undirected graph (although some rooms might be unreachable in the restricted version).

inputFormat

The input is given as follows:

 n m
 a b
 k r1 r2 ... rk
 u1 v1 C1
 u2 v2 C2
 ...
 um vm Cm

• The first line contains two integers \(n\) and \(m\): the number of rooms and corridors.
• The second line contains two integers \(a\) and \(b\): the room numbers of the two target rooms.
• The third line begins with an integer \(k\) (\(0 \le k \le n-1\)) denoting the number of restricted rooms, followed by \(k\) distinct integers \(r_1, r_2, \dots, r_k\). (Note: Room 1 is guaranteed to be accessible and will not be listed as restricted.)
• Each of the next \(m\) lines contains three integers \(u, v, C\) describing a bidirectional corridor between rooms \(u\) and \(v\) with cost \(C\).

outputFormat

Output a single integer: the minimum overall time required for Harry and Ron to cover the two target rooms (i.e. the maximum arrival time between them) or \(-1\) if it is impossible to reach both targets following the restrictions.

sample

5 6
3 4
1 2
1 2 3
1 3 4
2 3 1
2 4 2
3 5 1
4 5 3

5