#include <bits/stdc++.h>

using namespace std;

const int NUMAR_MAXIM_NODURI = 18;
const int INFINIT = 1000000000;
int numar_noduri, numar_muchii;
vector<vector<int>> cost(NUMAR_MAXIM_NODURI, vector<int>(NUMAR_MAXIM_NODURI, INFINIT));
vector<vector<int>> DP(NUMAR_MAXIM_NODURI, vector<int>((1 << NUMAR_MAXIM_NODURI) - 1, INFINIT));
vector<vector<int>> stari_binare(NUMAR_MAXIM_NODURI, vector<int>());


int numarBitiUnu(int numar)
{
    if(numar == 0)return 0;
    return (numar & 1) + numarBitiUnu(numar >> 1);
}

void initializareStartiBinare(int stare_binara_maxima)
{
    for(int stare_binara = 1; stare_binara <= stare_binara_maxima; ++stare_binara)
        stari_binare[numarBitiUnu(stare_binara)].push_back(stare_binara);
}


inline int bitCaracteristic(int nod){ return (1 << nod);}


inline bool nodInStareBinara(int nod, int stare_binara){ return (bitCaracteristic(nod) & stare_binara);}


int cicluHamiltonianCostMinim()
{
    initializareStartiBinare((1 << numar_noduri) - 1);

    int nod_start = 0;

    for(int nod_urmator = 0; nod_urmator < numar_noduri; ++nod_urmator)
    {
        if(nod_urmator == nod_start)
        {
            continue;
        }

        DP[nod_urmator][bitCaracteristic(nod_start) | bitCaracteristic(nod_urmator)] = cost[nod_start][nod_urmator];
    }


    for(int lungime_drum = 3; lungime_drum <= numar_noduri; ++lungime_drum)
    {
        for(auto& stare_binara_urmatoare : stari_binare[lungime_drum])
        {
            if(nodInStareBinara(nod_start, stare_binara_urmatoare) == false) continue;

            for(int nod_urmator = 0; nod_urmator < numar_noduri; ++nod_urmator)
            {
                if(nod_urmator == nod_start || nodInStareBinara(nod_urmator, stare_binara_urmatoare) == false) continue;

                int stare_binara_anerioara = (stare_binara_urmatoare ^ bitCaracteristic(nod_urmator));

                int distanta_minima = INFINIT;

                for(int nod_anterior = 0; nod_anterior < numar_noduri; ++nod_anterior)
                {
                    if(nod_anterior == nod_start || nod_anterior == nod_urmator || nodInStareBinara(nod_anterior, stare_binara_anerioara) == false) continue;

                    distanta_minima = min(distanta_minima, DP[nod_anterior][stare_binara_anerioara] + cost[nod_anterior][nod_urmator]);
                }

                DP[nod_urmator][stare_binara_urmatoare] = distanta_minima;
            }
        }
    }

    int stare_binara_finala = (1 << numar_noduri) - 1, cost_minim_drum = INFINIT;

    for(int nod_anterior = 0; nod_anterior < numar_noduri; ++ nod_anterior)
    {
        if(nod_anterior == nod_start) continue;

        cost_minim_drum = min(cost_minim_drum, DP[nod_anterior][stare_binara_finala] + cost[nod_anterior][nod_start]);
    }

    return cost_minim_drum;
}

int main()
{
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");

    fin >> numar_noduri >> numar_muchii;

    for(int i = 1; i <= numar_muchii; ++i)
    {
        int nod_plecare, nod_sosire, cost_muchie;

        fin >> nod_plecare >> nod_sosire >> cost_muchie;

        cost[nod_plecare][nod_sosire] = cost_muchie;
    }

    fout << cicluHamiltonianCostMinim();
}