#include <fstream>
#include <vector>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
const int N=18;
const int inf=1e9+1;
int n,m,d[1<<N][N],c[N][N];

int main()
{
    cin>>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++)
            d[j][i]=inf;
    }
    for(int i=1; i<=m; i++){
        int x,y;
        cin>>x>>y>>c[x][y];
    }
    d[1][0]=0;
    for(int i=1; i<(1<<n); i+=2){
        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;
                        d[x][k]=min(d[x][k],d[i][j]+c[j][k]);
                }
            }
        }
    }
    int rez=inf;
    for(int i=1; i<n; i++)
        if(c[i][0]!=inf)
            rez=min(rez, d[(1<<n)-1][i]+c[i][0]);
    if(rez==inf)
        cout<<"Nu exista solutie";
    else
        cout<<rez;
    return 0;
}