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

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







































vector<vector<int>> m;
array<array<int, 20>, 20> f;

int n, M, x, y, z;
void read();
void make_m();
int rez();

int main(){
    read();
    make_m();
    fout << rez();
    return 0;
}

void read(){
    fin >> n >> M;
    m = vector<vector<int>>(1 << n, vector<int>(n));
    for (auto &i : m){
        i.assign(i.size(), inf);
    }
    for (int i = 0; i < M; i++){
        fin >> x >> y >> z;
        f[x][y] = z;
    }
}

void make_m(){
    m[1][0] = 0;
    for (int i = 3; i < (1 << n); i=i+2){
        for (int nod = 1; nod < n; nod++){
            if ((i & (1 << nod)) != 0){
                for (int y = 0; y < n; y++){
                    if ((i & (1 << y)) != 0 && f[y][nod] != 0 && m[i-(1 << nod)][y] != inf)
                        m[i][nod] = min(m[i][nod], m[i-(1 << nod)][y] + f[y][nod]);
                }
            }
        }
    }
}

int rez(){
    int rez = inf;
    for (int nod = 1; nod < n; nod++){
        if (f[nod][0] != 0)
            rez = min(rez, m[(1 << n) - 1][nod] + f[nod][0]);
    }
    return rez;
}