#include<bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int INF = 0x3f3f3f3f;

int a[18][18];
int d[18][18][(1<<18)];
int n,m;

int main(){
    in>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        in>>x>>y>>c;
        a[x][y]=c;
    }
    for(int j=0;j<n;j++)
    for(int k=0;k<n;k++)
    for(int i=0;i<(1<<n);i++){
        d[j][k][i]=INF;
    }
    for(int i=0;i<n;i++){
        d[i][i][(1<<i)]=0;
    }
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++) if(i&(1<<j)){
            for(int e=0;e<n;e++) if(e!=j && i&(1<<e)){
                for(int f=0;f<n;f++) if(f!=e && i&(1<<f) && a[f][e]!=0){
                    d[j][e][i] = min(d[j][e][i], d[j][f][i^(1<<e)] + a[f][e] );
                }
            }
        }
    }
    int ans = INF;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) if(a[j][i]){
            ans = min(ans, d[i][j][(1<<n)-1] + a[j][i] );
        }
    }
    if(ans == INF) out<<"Nu exista solutie\n";
    else out<<ans<<'\n';
    return 0;
}