#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int N=18;
const int INF=1e9;
int n,m;
int dp[1<<N][N],c[N][N];
int main()
{
    f>>n>>m;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            c[i][j]=INF*(i!=j);
        for(int j=0; j<(1<<n); j++)
            dp[j][i]=INF;
    }
    for(int i=1; i<=m; i++){
        int x,y;
        f>>x>>y;
        f>>c[x][y];
    }
    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 x=(i | (1<<k));
                        dp[x][k]=min(dp[x][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)
        g<<"Nu exista solutie";
    else
        g<<rez;
    return 0;
}