#include <bits/stdc++.h>
#define N_MAX 2005
#define K_MAX 18

using namespace std;

ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");

vector < int > buff;

int N, M, K;
int x, y, d;

vector < pair < int, int > > G[N_MAX];
vector < int > fratii;

priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > PQ;
int D[N_MAX][N_MAX], vis[N_MAX];

void Dijkstra(int root)
{
    int currNode = PQ.top().second;
    int currCost = PQ.top().first;
    PQ.pop();
    while (PQ.size() && vis[currNode])
    {
        currNode = PQ.top().second;
        currCost = PQ.top().first;
        PQ.pop();
    }
    vis[currNode] = 1;
    for (pair < int, int > node: G[currNode])
        if (vis[node.second] == 0 && D[root][node.second] > currCost + node.first)
        {
            D[root][node.second] = currCost + node.first;
            PQ.push(make_pair(D[root][node.second], node.second));
        }
    if (PQ.size())
        Dijkstra(root);
}

int dp[(1 << K_MAX)][K_MAX];
int poz[N_MAX];

int main()
{
    fin >> N >> M;
    while (fin >> x)
        buff.push_back(x);
    reverse(buff.begin(), buff.end());
    for (int i = 1; i <= M; i++)
    {
        d = buff[3 * (i - 1)];
        y = buff[3 * (i - 1) + 1];
        x = buff[3 * (i - 1) + 2];
        G[x].push_back(make_pair(d, y));
        G[y].push_back(make_pair(d, x));
    }
    for (int i = 3 * M; i < buff.size(); i++)
        fratii.push_back(buff[i]);

    sort(fratii.begin(), fratii.end());
    if (fratii[fratii.size() - 1] != N);
        fratii.push_back(N);
    if (fratii[0] != 1)
        fratii.push_back(1);

    K = fratii.size();

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            D[i][j] = INT_MAX / 2;

    for (int i = 1; i <= N; i++)
    {
        D[i][i] = 0;
        PQ.push(make_pair(0, i));
        Dijkstra(i);
        for (int j = 1; j <= N; j++)
            vis[j] = 0;
    }

    for (int i = 1; i <= N; i++)
        G[i].clear();

    for (int i = 0; i < fratii.size(); i++)
        poz[fratii[i]] = i;

    for (int i = 0; i < fratii.size(); i++)
        for (int j = i + 1; j < fratii.size(); j++)
        {
            x = fratii[i];
            y = fratii[j];
            d = D[x][y];

            ///cout << x << " " << y << " " << d << "\n";

            G[x].push_back(make_pair(d, y));
            G[y].push_back(make_pair(d, x));
        }

    for (int mask = 0; mask < (1 << K); mask++)
        for (int i = 0; i < K; i++)
            dp[mask][i] = INT_MAX / 2;

    for (int i = 0; i < K; i++)
        dp[(1 << i)][i] = 0;

    ///cout << "\n";

    for (int mask = 0; mask < (1 << K); mask++)
        for (int i = 0; i < K; i++)
            if (mask & (1 << i))
            {
                int currNode = fratii[i];
                for (pair < int, int > node: G[currNode])
                    if ((mask & (1 << poz[node.second])) == 0)
                    {
                        dp[mask + (1 << poz[node.second])][poz[node.second]] = min(dp[mask + (1 << poz[node.second])][poz[node.second]], dp[mask][i] + node.first);
                        ///cout << mask << " " << poz[node.second] << " " << dp[mask + (1 << poz[node.second])][poz[node.second]] << "\n";
                    }
            }


    fout << dp[(1 << K) - 1][poz[N]] << "\n";
    return 0;
}