#include <bits/stdc++.h>
#define ll long long
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int inf = 2000000000;
int N,M,dp[(1 << 20)][20],a,b,c,i,j,bitmask,last,newmask,sol=inf;
int A[20][20];

int main(){
    fin >> N >> M;

    for (i = 1;i <= M;i++){
        fin >> a >> b >> c;
        A[a][b] = c;
    }

    for (i = 0;i < (1 << N);i++)
        for (j = 0;j < N;j++)
            dp[i][j] = inf;

    dp[1][0] = 0;

    for (bitmask = 1;bitmask < (1 << N);bitmask++){
        for (i = 0;i < N;i++){
            if (bitmask & (1 << i)){
                for (j = 0;j < N;j++)
                    if (!((1 << j) & bitmask) && A[i][j]){
                        newmask = (bitmask ^ (1 << j));

                        dp[newmask][j] = min(dp[newmask][j],dp[bitmask][i] + A[i][j]); 
                    }
            }
        }
    }

    for (i = 0;i < N;i++)
        if (A[i][0])
            sol = min(sol,dp[(1 << N) - 1][i] + A[i][0]);
    

    if (sol == inf)
        fout << "Nu exista solutie";
    else
        fout << sol;
}