都市 \(1,N\) では必ずライブを行うので、都市 \(1,N\) にライブ会場がない場合を考え、都市 \(1,N\) 以外の \(2\) つの会場でライブを行うことを考えます。

\(d[k][i]\) を「すでに \(k\) 会場でライブを行い、現在都市 \(i\) にいる場合の移動距離の最小値」 \((k=0,1,2,\ i=1,2,\ldots,N)\) とします。初期値は \(d[0][1]=0\) で、求める値は \(d[2][N]\) です。

この \(d[k][i]\) はダイクストラ法を拡張することで求めることができます。いわゆる頂点倍化・拡張ダイクストラなどと呼ばれるもので、まだライブをしていないライブ会場に到達した場合に \(k\) を \(1\) 増やすことでダイクストラ法を用いて \(d[2][N]\) の値を求めることができます。

\(k=1\) の場合、既にライブを行った都市はどこかを持ち、さらに最小値を上位 \(2\) つまで持つ必要があることに注意してください。

実装例(Python3)

import sys
from heapq import *

input = sys.stdin.readline
n, m, k = map(int, input().split())
aa = list(map(int, input().split()))
a = [False] * n
for i in aa:
    a[i - 1] = True
a[0] = a[-1] = False
g = [[] for _ in range(n)]
for _ in range(m):
    u, v, c = map(int, input().split())
    u, v = u - 1, v - 1
    g[u].append((v, c))
    g[v].append((u, c))
INF = 10**18
d0 = [INF] * n
d1 = [(INF, -1)] * n
d2 = [(INF, -1)] * n
d3 = [INF] * n
hq = []
heapify(hq)
heappush(hq, (0, 0, 0, -1))
d0[0] = 0


def chmin0(idx, val):
    if d0[idx] > val:
        d0[idx] = val
        return True
    return False


def chmin1(idx, val, aa):
    if d1[idx][1] == aa:
        if d1[idx][0] > val:
            d1[idx] = (val, aa)
            return True
        return False
    if d2[idx][1] == aa:
        if d2[idx][0] > val:
            d2[idx] = (val, aa)
            return True
        return False
    if d1[idx][0] > val:
        d2[idx] = d1[idx]
        d1[idx] = (val, aa)
        return True
    if d2[idx][0] > val:
        d2[idx] = (val, aa)
        return True
    return False


def chmin2(idx, val):
    if d3[idx] > val:
        d3[idx] = val
        return True
    return False


while hq:
    min_cost, ty, idx, aa = heappop(hq)
    if ty == 0:
        if d0[idx] != min_cost:
            continue
        for to, c in g[idx]:
            cost = min_cost + c
            if a[to]:
                if chmin1(to, cost, to):
                    heappush(hq, (cost, 1, to, to))
            else:
                if chmin0(to, cost):
                    heappush(hq, (cost, 0, to, -1))
    if ty == 1:
        if d1[idx] != (min_cost, aa) and d2[idx] != (min_cost, aa):
            continue
        for to, c in g[idx]:
            cost = min_cost + c
            if a[to] and aa != to:
                if chmin2(to, cost):
                    heappush(hq, (cost, 2, to, -1))
            else:
                if chmin1(to, cost, aa):
                    heappush(hq, (cost, 1, to, aa))
    if ty == 2:
        if d3[idx] != min_cost:
            continue
        for to, c in g[idx]:
            cost = min_cost + c
            if chmin2(to, cost):
                heappush(hq, (cost, 2, to, -1))
print(d3[-1])