#include <bits/stdc++.h>
std::ifstream fin("hamilton.in");
std::ofstream fout("hamilton.out");
int n, m, ret=INT_MAX;
int sol[20][131100], costs[20][20];
int solve(int last, int config);
int main()
{
    fin>>n>>m;
    while(m--){
        int x, y, z;
        fin>>x>>y>>z;
        costs[x][y]=z;
    }
    if(n<=2) {
        fout<<"Nu exista solutie";
        return 0;
    }
    for(int i=0; i<n-1; ++i) sol[i+1][1<<i]=costs[0][i+1];
    for(int i=1; i<n; ++i){
        if(!costs[i][0]) continue;
        int v=solve(i, (1<<(n-1))-1);
        if(v)ret=std::min(ret, v+costs[i][0]);
    }
    if(ret!=INT_MAX) fout<<ret;
    else fout<<"Nu exista solutie";
    return 0;
}
int solve(int last, int config){
    if(sol[last][config]) return sol[last][config];
    sol[last][config]=INT_MAX;
    int cpy=config;
    for(int i=0; i<n-1; ++i) {
        if(cpy&1){
            if(!costs[i+1][last]) continue;
            int v=solve(i+1, config^(1<<(last-1)));
            if(v!=INT_MAX) sol[last][config]=std::min(sol[last][config], v+costs[i+1][last]);
        }
        cpy>>=1;
    }
    return sol[last][config];
}