#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 18;
const int INF = 1e9;

int dp[1<<N][N];
int c[N][N];

int main()
{
    int x, y;
    int n, m;
    in>>n>>m;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i!=j)
                c[i][j]=INF;
        }
    }
    for(int i=0; i<=m; i++)
    {
        in>>x>>y;
        in>>c[x][y];
    }
    for(int i=0; i<(1<<n); i++)
    {
        for(int j=0; j<n; j++)
        {
            dp[i][j]=INF;
        }
    }
    dp[1][0]=0;
    for(int i = 1; i< (1<<n); i+=2)
    {
        for(int j=0; j<n; j++)
        {
            if((1<<j)&i)//j apartine i, deci are sens dp[i][j]
            {
                for(int k=0; k<n; k++)
                {
                    if (!((1 << k) & i) && c[j][k] != INF)//k e un succesor al lui j
                    {
                        int ii=(i | (1<<k));
                        dp[ii][k] = min(dp[ii][k], dp[i][j] + c[j][k]);
                    }
                }
            }
        }
    }
    int rez = INF;
    for (int j = 1; j < n; j++)
    {
        if (c[j][0] != INF)
        {
            rez = min(rez, dp[(1<<n) - 1][j] + c[j][0]);
        }
    }
    if (rez == INF)
    {
        out << "Nu exista solutie";
    }
    else
    {
        out << rez;
    }
    return 0;
}