#include <bits/stdc++.h>


using namespace std;

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

const short Nmax = 19;

const int Vmax = 1e9;

int dp[Nmax][(1 << (Nmax - 1)) + 1], n, m, cost[Nmax][Nmax];


vector < int > L[Nmax];

struct T
{
    int nod, stare , cost;
    bool operator < (const T &e) const
    {
        return cost > e.cost;
    }
};

priority_queue < T > Q;

int main()
{
    int x, y, c;
    T w;
    fin >> n >> m;
    for(int i = 0 ; i < n  ; i++)
        for(int j = 1 ; j <= (1 << n) - 1 ; j++)
            dp[i][j] = Vmax;
    for(int i = 0 ; i < n ; i++)
        for(int j = 0 ; j < n ; j++)
            cost[i][j] = Vmax;
    for(int i = 1 ; i <= m ; i++)
    {
        fin >> x >> y >> c;
        cost[x][y] = min(cost[x][y], c);
        L[x].push_back(y);
    }
    Q.push({0, 1 , 0});
    dp[0][1] = 0;
    while(!Q.empty())
    {
        w = Q.top();
        Q.pop();
        for(auto it : L[w.nod])
        {
            if(!(w.stare & (1 << it)) && dp[it][w.stare | (1 << it)] > dp[w.nod][w.stare] + cost[w.nod][it])
            {
                dp[it][w.stare | (1 << it)] =  dp[w.nod][w.stare] + cost[w.nod][it];
                Q.push({it, w.stare | (1 << it) , dp[it][w.stare | (1 << it)]});
            }
        }
    }
    int ans = Vmax;
    for(int i = 1 ; i < n ; i++)
        ans = min(ans, dp[i][(1 << n) - 1] + cost[i][0]);
    if(ans == Vmax)
        fout << "Nu exista solutie\n";
    else fout << ans << "\n";
    fin.close();
    fout.close();
}