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

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

const int NMAX = 18;
const int INF = 0x3F3F3F3F;

int n,m;
int graf[NMAX + 1][NMAX + 1];
int dp[NMAX + 1][1 << NMAX];

void read(){
    fin >> n >> m;
    for(int i = 1;i<=m;++i){
        int x,y,c;
        fin >> x >> y >> c;
        graf[x][y] = c;
    }
}

int hamilton(int nod,int config){
    if(config == 0){
        if(graf[nod][0])
            return graf[nod][0];
        return INF;
    }
    if(dp[nod][config])
        return dp[nod][config];
    
    int min_cost = INF;
    for(int i = 0;i < n;++i)
        if(((1 << i) & config) && graf[nod][i]){
            int new_config = config ^ (1 << i);
            int new_cost = graf[nod][i] + hamilton(i, new_config);
            min_cost = min(min_cost, new_cost);
        }
    return (dp[nod][config] = min_cost);
}

int main(){

    read();
    int config = (1 << n) - 1 - 1;
    int ans = hamilton(0, config);
    if(ans != INF)
        fout << ans;
    else
        fout << "nu exista solutie";
    return 0;
}