#include <bits/stdc++.h>
#define INF 1000000000
std::ifstream fin("hamilton.in");
std::ofstream fout("hamilton.out");
int n, m, ret=INF;
int sol[20][131100], costs[20][20];
std::vector<int> graph[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;
        graph[y].push_back(x);
    }
    for(int i=0; i<n-1; ++i) sol[i+1][1<<i]=costs[0][i+1];
    for(auto it:graph[0]){
        ret=std::min(ret, std::min(INF, solve(it, (1<<(n-1))-1))+costs[it][0]);
    }
    if(ret!=INF) 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]=INF;
    for(auto it:graph[last])if(config&(1<<(last-1))){
        sol[last][config]=std::min(sol[last][config], std::min(INF, solve(it, config^(1<<(last-1)))+costs[it][last]));
    }
    return sol[last][config];
}