#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMAX=20;
const int CONFMAX=(1<<18)+5;
const int inf=2e9;

int N, M, cost[NMAX][NMAX], dp[CONFMAX][NMAX], sol;
vector<int> g[NMAX];

/// dp[conf][i]=costul minim de a ajunge din nodul de start(1) la nodul i
/// folosind doar nodurile din configuratie exact o data

/// dp[conf][i]=min{dp[conf fara j][j]+cost[j][i] / j nodurile din care putem ajunge la i}

int calculate(int conf, int nod)
{
    if(dp[conf][nod]!=-1)
        return dp[conf][nod];
    dp[conf][nod]=inf;
    for(auto x: g[nod]){

        if(conf&(1<<x)){ // x se afla in configuratie
            if(x==0 and conf!=((1<<nod)+1))
                continue;
            dp[conf][nod]=min(dp[conf][nod],calculate(conf^(1<<nod),x)+cost[x][nod]);
        }
    }
    return dp[conf][nod];
}

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

    int x, y, z;
    for(int i=1;i<=M;i++){
        fin>>x>>y>>z;
        g[y].push_back(x);
        cost[x][y]=z;
    }

    for(int i=0;i<CONFMAX;i++)
        for(int j=0;j<N;j++)
            dp[i][j]=-1;
    dp[1][0]=0;

    sol=inf;
    for(auto x: g[0])
        sol=min(sol,calculate(((1<<N)-1),x)+cost[x][0]);

    if(sol==inf)
        fout<<"Nu exista solutie";
    else
        fout<<sol;

    fin.close();
    fout.close();
    return 0;
}