#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <bitset>

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

int n, m;
int adiacenta[18][18];
const int N_max = 1 << 18;

void update(int x, int y, int val) {
    adiacenta[x][y] = val;
}
void reading() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, val;
        fin >> x >> y >> val;
        update(x, y, val);
    }
}

long long dp[18][N_max];

void populate(int sl, int fl, int sc, int fc, int val){
    for(int i =sl; i <= fl; i++){
        for(int j = sc; j <= fc; j++){
            dp[i][j] = val;
        }
    }
}
long long MiN(int x, int y){
    return (x > y? y : x);
}
int main() {
    reading();

    populate(0, 17, 0, N_max - 1, -1);
    dp[0][1] = 0;
    int nr = (1 << n) - 1;
    for(int masc = 1; masc <= nr; masc ++){
        bitset<18> biti(masc);
        for(int i = 0; i <= n - 1; i++){
            if(biti[i] == 0 || dp[i][masc] == -1)continue;
            for(int j = 0; j <= n - 1; j++){
                if(biti[j] == 0 && adiacenta[i][j] != 0){
                    if(dp[j][masc + (1 << j)] == -1)dp[j][masc + (1 << j)] = dp[i][masc] + adiacenta[i][j];
                    else{
                        dp[j][masc + (1 << j)] = min(dp[j][masc + (1 << j)], dp[i][masc] + adiacenta[i][j]);
                    }
                }
            }

        }
    }
    long long min = -1;
    for(int i = 1; i < n; i++){
        if(dp[i][nr] != -1 && adiacenta[i][0] != 0){
            if(min == -1) min = dp[i][nr] + adiacenta[i][0];
            else min = MiN(min, dp[i][nr] + adiacenta[i][0]);
        }
    }
    fout << min;

}