#include <fstream>
#include <cstdio>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,viz[20],x,y,z,perm[20],adi[20][20],cost=1e9,dp[ (1<<17)+1][20];
bool ok;
vector<pair<int,int>>v[20];
void bkt( int k, int pret){
     if(k==n){
                if(adi[perm[n-1]][perm[0]]){
                    ok=1;
                    cost=min(cost,pret+adi[perm[n-1]][0]);
                }
                return;
            }
    for(int i=1;i<n;++i){
        if(!viz[i]){
            viz[i]=1;
            perm[k]=i;
            if(k==1){
                if(adi[0][perm[k]])
                    bkt(k+1,adi[0][perm[k]]);
                viz[i]=0;
            }
            else{
                if(adi[perm[k-1]][perm[k]])
                    bkt(k+1,pret+adi[perm[k-1]][perm[k]]);
                viz[i]=0;
            }
        }

    }
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>z;
        adi[x][y]=z;
    }
    //bkt(1,0);
    for(int i=1;i<=(1<<(n-1));++i)
    {
        for(int j=1;j<=n;++j) dp[i][j]=1e9;
    } 
    for(int i=1;i<n;i++){
        if(adi[0][i])
            dp[1<<(i-1)][i] = adi[0][i];
    }

    for(int msk=1;msk<(1<<(n-1));++msk){
        for(int i=1;i<n;++i){
            if(msk &(1<< (i-1))){
                for(int j=1;j<n;++j){
                    if(j==i) continue;
                    if(msk & (1<<(j-1))){
                        if(adi[j][i])
                            dp[msk][i]=min(dp[msk][i],dp[msk- (1<<(i-1))][j]+adi[j][i]);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;++i)
    {
        if(adi[i][0]){
            ok=1;
            cost=min(cost,dp[(1<<(n-1))-1][i]+adi[i][0]);
        }
    }
    if(ok)
        fout<<cost;
    else fout<<"Nu exista solutie";
    return 0;
}