#include <bits/stdc++.h>
#define DMAX 25
#define LgMAX 262150

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

list <int> V[DMAX];

int M[DMAX][DMAX];
int dp[LgMAX][DMAX];

int n,m,sol=INT_MAX/2;

inline int minim(int x,int y){
    if(x<y)
       return x;
    return y;
}

int main(){
    int i,j,x,y,z;
    fin>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            M[i][j]=INT_MAX/2;
    for(i=1;i<=m;i++){
        fin>>x>>y>>z;
        V[y].push_back(x);
        M[x][y]=z;
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            dp[i][j]=INT_MAX/2;
    dp[1][0]=0;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            if(i & (1<<j)){
               for(auto& k:V[j])
                   if(i & (1<<k))
                      dp[i][j]=minim(dp[i][j],dp[i^(1<<j)][k]+M[k][j]);
            }
    for(auto& i:V[0])
        sol=minim(sol,dp[(1<<n)-1][i]+M[i][0]);

    if(sol == INT_MAX/2)
       fout<<"Nu exista solutie\n";
       else
       fout<<sol<<'\n';

    return 0;
}