#include <fstream>
#include <climits>
#include <vector>
#define push push_back

using namespace std;

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

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

int n,m,x,y,c,ans,mask,i,j;
int cost[N][N],dp[(1<<N)][N];

vector<int> nod[N];

void init()
{
    for(i=0; i<n; i++)
        for(j=0; j<n; j++)
            cost[i][j]=INF;
    for(i=0; i<(1<<n); i++)
        for(j=0; j<n; j++)
            dp[i][j]=INF;
    ans=INF;
}

int main()
{
    fin>>n>>m; init();
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        cost[x][y]=c;
        nod[y].push(x);
    }

    dp[1][0]=0;
    for(mask=0; mask<(1<<n); mask++)
        for(j=0; j<n; j++)
            if(mask&(1<<j))
                for(auto k:nod[j])
                    if(mask&(1<<k))
                        dp[mask][j]=min(dp[mask][j],dp[mask^(1<<j)][k]+cost[k][j]);

    for(auto k:nod[0])
        ans=min(ans,dp[(1<<n)-1][k]+cost[k][0]);

    if(ans==INF)
        fout<<"Nu exista solutie\n";
    else
        fout<<ans;
    return 0;
}