Why this algorithm fails for some of the test case from heapq import heappush, heappop
def solve():
  n, m, h = map(int, input().split())
  horses = set(list(map(int, input().split())))
  edges = [list(map(int, input().split())) for _ in range(m)]

  adj = [[] for _ in range(n+1)]
  for u, v, w in edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

  shortest = [[float('inf')] * 2 for _ in range(n + 1)] # 0 for R and 1 for M

  def dijkstra(start, who):
  
    shortest[start][who] = 0
    no_horse, with_horse = set(), set() # track nodes that have been visited with/without horse
    
    if start in horses:
      with_horse.add(start)
      queue = [(0, start, 1)]
    else:
      no_horse.add(start)
      queue = [(0, start, 0)]

    while queue:
      dist, node, horse = heappop(queue)
  
      for neigh, weight in adj[node]:
        if not horse:
          if neigh in horses:
            if dist + weight > shortest[neigh][who] and neigh in with_horse:
              continue
           
            if dist + weight <= shortest[neigh][who]:
              shortest[neigh][who] = dist + weight
            else:
              with_horse.add(neigh)

            heappush(queue, (dist + weight, neigh, 1))
            
          else:
            if dist + weight > shortest[neigh][who] and neigh in no_horse:
              continue

            if dist + weight <= shortest[neigh][who]:
              shortest[neigh][who] = dist + weight
            else:
              no_horse.add(neigh)

            heappush(queue, (dist + weight, neigh, 0))
        else:
          if dist + weight // 2 > shortest[neigh][who] and neigh in with_horse:
            continue

          if dist + weight // 2 <= shortest[neigh][who]:
            shortest[neigh][who] = dist + weight // 2
          else:
            with_horse.add(neigh)

          heappush(queue, (dist + weight // 2, neigh, 1))

  dijkstra(1, 0)
  dijkstra(n, 1)
  res = float('inf')
  for i in range(1, n + 1):
    res = min(res, max(shortest[i][0], shortest[i][1]))

  print(res if res != float('inf') else -1)


for _ in range(int(input())):
    solve()
; which is used to solve this problem: 
 Marian sold her last ware at the Market at the same time Robin finished training at the Major Oak. They couldn't wait to meet, so they both start without delay.

The travel network is represented as 𝑛 vertices numbered from 1 to 𝑛 and 𝑚 edges. The 𝑖-th edge connects vertices 𝑢𝑖 and 𝑣𝑖, and takes 𝑤𝑖 seconds to travel (all 𝑤𝑖 are even). Marian starts at vertex 1 (Market) and Robin starts at vertex 𝑛 (Major Oak).

In addition, ℎ of the 𝑛 vertices each has a single horse available. Both Marian and Robin are capable riders, and could mount horses in no time (i.e. in 0 seconds). Travel times are halved when riding. Once mounted, a horse lasts the remainder of the travel. Meeting must take place on a vertex (i.e. not on an edge). Either could choose to wait on any vertex.

Output the earliest time Robin and Marian can meet. If vertices 1 and 𝑛 are disconnected, output −1 as the meeting is cancelled.

Input
The first line of the input contains a single integer 𝑡 (1≤𝑡≤104) — the number of test cases.

The first line of each test case consists of three integers 𝑛, 𝑚, ℎ (2≤𝑛≤2⋅105,1≤𝑚≤2⋅105,1≤ℎ≤𝑛) — the number of vertices, the number of edges and the number of vertices that have a single horse.

The second line of each test case contains ℎ distinct integers 𝑎1,𝑎2,…,𝑎ℎ (1≤𝑎𝑖≤𝑛) — the vertices that have a single horse available.

Then follow 𝑚 lines of each test case, each with three integers 𝑢𝑖, 𝑣𝑖, 𝑤𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛,2≤𝑤𝑖≤106) — meaning that there is an edge between vertices 𝑢𝑖 and 𝑣𝑖 with travel cost 𝑤𝑖 seconds without a horse.

There are no self loops or multiple edges. By good fortune, all 𝑤𝑖 are even integers.

It is guaranteed that the sums of both 𝑛 and 𝑚 over all test cases do not exceed 2⋅105.

Output
For each test case, output a single integer, the earliest time Robin and Marian can meet. If it is impossible for them to meet, output −1.

Example
inputCopy
6
2 1 1
1
1 2 10
3 1 2
2 3
1 2 10
3 3 1
2
1 2 4
1 3 10
2 3 6
4 3 2
2 3
1 2 10
2 3 18
3 4 16
3 2 1
2
1 2 4
1 3 16
7 7 1
3
1 5 2
2 6 12
1 2 12
6 4 8
7 3 4
6 3 4
7 6 4
outputCopy
5
-1
6
19
14
12
Note
In the first test case, Marian rides from vertex 1 to vertex 2, Robin waits.

In the second test case, vertices 1 and 3 are not connected.

In the third test case, both Marian and Robin travel to vertex 2 to meet.

In the fourth test case, Marian travels to vertex 2 without a horse, mounts the horse at vertex 2 and rides to vertex 3 to meet Robin.

In the fifth test case, Marian travels to vertex 2 without a horse, mounts the horse at vertex 2 and rides back to vertex 1 and then to vertex 3. Robin waits.