#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int INF = 1e9 + 7;
int nr_noduri, nr_muchii;
vector<pair<int, int>> v[18];
int dp[1 << 18][18];

int main()
{
    fin >> nr_noduri >> nr_muchii;
    int x, y, c;
    for(int i = 1; i <= nr_muchii; i++)
    {
        fin >> x >> y >> c;
        v[x].push_back({y, c});
    }

    int total_stari = 1 << nr_noduri;

    for(int conf = 0; conf < total_stari; conf++)
    {
        for(int i = 0; i < nr_noduri; i++)
        {
            dp[conf][i] = INF;
        }
    }

    dp[1][0] = 0;

    for(int conf = 1; conf < total_stari; conf++)
    {
        for(int u = 0; u < nr_noduri; u++)
        {
            if(dp[conf][u] != INF)
            {
                for(auto arc : v[u])
                {
                    int vecin = arc.first;
                    int cost = arc.second;
                    int conf_noua = conf ^ (1 << vecin);

                    if(conf_noua > conf)
                    {
                        dp[conf_noua][vecin] = min(dp[conf_noua][vecin], dp[conf][u] + cost);
                    }
                }
            }
        }
    }

    int masca_finala = total_stari - 1;
    int cost_minim = INF;

    for(int i = 0; i < nr_noduri; i++)
    {
        if(dp[masca_finala][i] != INF)
        {
            for(auto arc : v[i])
            {
                if(arc.first == 0)
                {
                    cost_minim = min(cost_minim, dp[masca_finala][i] + arc.second);
                }
            }
        }
    }

    if(cost_minim == INF)
    {
        fout << "Nu exista solutie\n";
    }
    else
    {
        fout << cost_minim << "\n";
    }

    return 0;
}