#include <bits/stdc++.h>
#define NMAX 18
#define INFINIT 1000000000
using namespace std;

ifstream fin{"hamilton.in"};
ofstream fout{"hamilton.out"};

vector<vector<int>> cost(NMAX, vector<int>(NMAX, INFINIT));
vector<vector<int>> dp(NMAX, vector<int>(1 << NMAX, INFINIT));

int numar_noduri, numar_muchii;

int main()
{
    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;
    }

    int nod_start = 0;
    int numar_stari = (1 << numar_noduri) - 1;

    dp[nod_start][1] = 0;

    for(int stare_curenta = 1; stare_curenta <= numar_stari; ++stare_curenta)
    {
        if((stare_curenta & (1 << nod_start)) == false) continue;

        for(int nod_curent = 0; nod_curent < numar_noduri; ++nod_curent)
        {
            if(nod_curent == nod_start || (stare_curenta & (1 << nod_curent)) == false) continue;

            int stare_anterioara = stare_curenta ^ (1 << nod_curent);

            for(int nod_anterior = 0; nod_anterior < numar_noduri; ++nod_anterior)
            {
                if(nod_anterior == nod_curent || (stare_anterioara & (1 << nod_anterior)) == false) continue;

                dp[nod_curent][stare_curenta] = min(dp[nod_curent][stare_curenta], dp[nod_anterior][stare_anterioara] + cost[nod_anterior][nod_curent]);
            }
        }
    }

    int minTur = INFINIT, stare_finala = (1 << numar_noduri) - 1;

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

        minTur = min(minTur, dp[nod_anterior][stare_finala] + cost[nod_anterior][nod_start]);
    }

    if(minTur == INFINIT)
    {
        fout << "Nu exista solutie";
    }
    else
    {
        fout << minTur;
    }

}