#include <fstream>
#include <climits>

using namespace std;
const int Vmax = 20;
int n, m, dp[Vmax][(1<<18)], cost[Vmax][Vmax];
int sol = INT_MAX;
int main(){
    ifstream fin("hamilton.in");
    ofstream fout("hamilton.out");
    fin>>n>>m;
    if(n==1){
        fout<<0;
        return 0;
    }
    for(int i=1;i<=m;i++){
        int x, y;
        fin>>x>>y>>cost[x][y];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<(1<<n);j++){
            dp[i][j]=INT_MAX;
        }
    }
    dp[0][1] = 0;
    for(int i=0;i<n;i++){
        for(int j=1;j<(1<<n);j++){
            if(dp[i][j]==INT_MAX)
                continue;
            for(int k=0;k<n;k++){
                if(!((1 << k) & j) && cost[i][k])
                    dp[k][j+(1<<k)] = min(dp[k][j+(1<<k)], dp[i][j]+cost[i][k]);
            }
        }
    }
    for(int i=1;i<n;i++){
        if(cost[i][0])
            sol = min(sol, dp[i][(1<<n)-1] + cost[i][0]);
    }
    if(sol==INT_MAX)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}