#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

const int N = 18;

int n,m,dp[N+1][1<<N],cst[N][N];

int main()
{
    F>>n>>m;
    memset(cst,0x3f,sizeof(cst));
    memset(dp,0x3f,sizeof(dp));
    for (int i=1,x,y,c;i<=m;++i)
    {
        F>>x>>y>>c;
        ++x; ++y;
        cst[x][y] = c;
    }
    dp[1][1] = 0;
    for (int c=1;c<(1<<n);++c)
        if ( c & 1 )
            for (int i=1;i<=n;++i)
                if ( (1<<(i-1)) & c )
                    for (int j=1;j<=n;++j)
                        if ( j != i && ( (1<<(j-1) ) & c ) )
                            dp[i][c] = min(dp[i][c],dp[j][c^(1<<(i-1))]+cst[j][i]);
    int ans = 1<<30;
    for (int i=2;i<=n;++i)
        ans = min(ans,dp[i][(1<<n)-1]+cst[i][1]);
    if ( ans >= 1000000000 )
        G<<"Nu exista solutie\n";
    else
        G<<ans<<'\n';
}