/*#include <iostream>
#include <fstream>
#include <list>
#include <map>

struct City
{
public:
    std::list<int> connectedCities = {};

public:
    void Add(const int id)
    {
        connectedCities.push_back(id);
    }
};

City* GetCity(std::map<int, City*>& cities, const int id)
{
    if (cities[id] != NULL)
        return cities[id];

    City newCity = City();
    cities[id] = &newCity;
    return &newCity;
}

int main()
{
    std::ifstream fIn("ubuntzei.txt");

    int destinationsNum, streetsNum;
    fIn >> destinationsNum >> streetsNum;

    std::map<int, City*> cities;

    int id;
    fIn >> id;

    auto* city = GetCity(cities, id);
    for (int i = 0; i < 2; i++)
    {
        fIn >> id;
        city->connectedCities.push_back(id);
        city->Add(id);
        GetCity(cities, id);
    }

    while (fIn >> id)
    {
        city = GetCity(cities, id);
        for (int i = 0; i < 2; i++)
        {
            fIn >> id;
            city->Add(id);
            GetCity(cities, id);
        }
    }
    for (auto& city : cities)
        std::cout << city.first << std::endl;
    return 0;
    for (auto& city : cities)
    {
        for (auto& connectedCity : city.second->connectedCities)
        {
            if (connectedCity == city.first)
                continue;

            city.second->Add(connectedCity);
        }
    }

    return 0;
}*/

#include <iostream>
#include <fstream>
#include <list>
#include <map>

struct City
{
public:
    int y, z;

public:
    City(int newY, int newZ)
    {
        y = newY;
        z = newZ;
    }
};

int Move(int cityIndex, int parent, City parentCache);

std::map<int, std::list<City>> cities;
std::list<int> toGoDestinations;

int destination;

int main()
{
    std::ifstream fIn("ubuntzei.in");

    // N M
    int streetsNum;
    fIn >> destination >> streetsNum;
    // ===
    
    // K
    int x, xCache;
    fIn >> xCache;

    while (fIn >> x)
    {
        if (x != xCache + 1)
            break;

        toGoDestinations.push_back(x);
        xCache = x;
    }
    // ===
    
    // X Y Z
    int y, z;
    fIn >> y >> z;
    cities[x].push_back(City(y, z));
    cities[y].push_back(City(x, z));

    while (fIn >> x)
    {
        fIn >> y >> z;
        cities[x].push_back(City(y, z));
        cities[y].push_back(City(x, z));
    }

    std::ofstream fOut("ubuntzei.out");
    fOut << Move(1, 0, City(0, 0));
  
    return 0;
}

int Move(int cityIndex, int parent, City parentCache)
{
    int minLength = 99;

    bool found = false;
    for (auto& city : cities[cityIndex])
    {
        int length = 0;

        if (city.y == 1)
            continue;

        if (city.y == parentCache.y)
            continue;

        parent++;
        if (parent == 2)
        {
            parentCache = city;
            parent = 0;
        }

        length += city.z;

        for (int dest : toGoDestinations)
        {
            if (city.y == dest)
            {
                toGoDestinations.remove(dest);
                break;
            }
        }
        if(cityIndex == 0){}
        if (city.y != destination || toGoDestinations.size() != 0)
            length += length + Move(city.y, parent, parentCache);

        if (length < minLength)
            minLength = length;
    }

    return minLength;
}