#include <bits/stdc++.h>

using namespace std;

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

constexpr int NMAX=20, MMAX=1048576/4;

vector <int> G[NMAX];

int N, M, i, j, X, Y, Z;

int Cost[NMAX][NMAX];

int dp[MMAX][NMAX];

int ans=INT_MAX;

int Solve (int X, int Y)
{
    if(dp[X][Y] == -1)
    {
        dp[X][Y]=0x3f3f3f3f;

        for(int i=0; i<G[Y].size(); ++i)
            if(X & (1<<G[Y][i]))
            {
                /*if(!G[Y][i] && X != ((1<<Y)+1))
                    continue;*/

                dp[X][Y]=min(dp[X][Y], Solve(X^(1<<Y), G[Y][i])+Cost[G[Y][i]][Y]);
            }
    }

    return dp[X][Y];
}

int main()
{
    f>>N>>M;

    // Indexare de la 0:
    for(i=0; i<N; ++i)
        for(j=0; j<N; ++j)
            Cost[i][j]=INT_MAX;

    for(i=0; i<MMAX; ++i)
        for(j=0; j<NMAX; ++j)
            dp[i][j]=-1;


    for(i=1; i<=M; ++i)
    {
        f>>X>>Y>>Z;

        G[Y].push_back(X);

        Cost[X][Y]=Z;
    }

    dp[1][0]=0;

    for(i=0; i<G[0].size(); ++i)
        ans=min(ans, Solve((1<<N)-1, G[0][i])+Cost[G[0][i]][0]);

    if(ans == INT_MAX)
        g<<"Nu exista solutie";
    else g<<ans;

    g<<'\n';
}