#include<bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int inf=1e9, NMAX=18;
int n,m,ans;
vector<vector<int> > graph(NMAX+5,vector<int>(NMAX+5,inf)), dp((1<<(NMAX)),vector<int>(NMAX+5, inf));
int hamilton(){
    dp[1][0]=0;
    for(int mask=2;mask<(1<<n);mask++){
        if(mask&1){
            for(int i=0;i<n;i++){
                if(mask&(1<<i)){
                    for(int j=0;j<n;j++){
                        if(mask&(1<<j)){
                            dp[mask][i]=min(dp[mask][i],dp[mask^(1<<i)][j]+graph[j][i]);
                        }
                    }
                }
            }
        }
    }
    int ans=inf;
    for(int i=0;i<n;i++){
        ans=min(ans,dp[(1<<n)-1][i]+graph[i][0]);
    }
    if(ans==inf){
        return -1;
    }
    return ans;
}
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        fin>>x>>y>>z;
        graph[x][y]=z;
    }
    ans=hamilton();
    if(ans==-1){
        fout<<"Nu exista solutie";
    }else{
        fout<<ans;
    }
}