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

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

int N,M,dp[(1 << 20)][20],a,b,c,i,j,bitmask,last,newmask,sol=1000000000;
int A[20][20];
deque< pair<int,short int> > dq;
bool found;

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

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

    dq.push_back({1,0});

    while (!dq.empty()){
        bitmask = dq.front().first;
        last = dq.front().second;

        for (int i = 0;i < N;i++){
            if ((bitmask == ((1 << N) - 1)) && A[last][i] != 0 && i == 0){
                sol = min(sol,dp[bitmask][last] + A[last][i]);
                found = 1;
            }

            if ((bitmask & (1 << i)) == 0 && A[last][i] != 0){
                newmask = (bitmask | (1 << i));

                dp[newmask][i] = min(dp[newmask][i],dp[bitmask][last] + A[last][i]);
                
                dq.push_back({newmask,i});
            }
        }
        
        dq.pop_front();
    }

    if (!found)
        fout << "Nu exista solutie";
    else
        fout << sol;
}