#include <iostream>
#include <fstream>
#define inf 1000000001
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
const int N=19;
int n,m,c[N][N],dp[1<<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=1; 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++){
        for(int j=0; j<n; j++){
            if((1<<j)&i){
                for(int k=0; k<n; k++)
                    if(!((1<<k)&i) && c[j][k]!=inf){
                        int x=(1<<k)|i;
                        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;
}