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

using namespace std;

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

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 = 0; conf < total_stari; conf++)
    {
        for(int i = 0; i < nr_noduri; i++)
        {
            dp[conf][i] = INF;
        }
    }
    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[u])
            {
                if(arc.first == 0)
                {
                    cost_minim = min(cost_minim, dp[masca_finala][u] + arc.second);
                }
            }
        }
    }
    if(cost_minim == INF)
        cout << "Nu exista solutie" << '\n';
    else
        cout << cost_minim << '\n';

    return 0;
}