#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 20;
const int INF = (1<<30);

int N; int M; int cost[NMAX][NMAX];

int D[1 << NMAX][NMAX];


vector<int> father[NMAX];

void read() {

    fin >> N >> M;
    while(M--) {

        int x; int y; int c;
        fin >> x >> y >> c;
        father[y].push_back(x);
        cost[x][y] = c;

    }
}

int compute(int state, int last) {

    if(D[state][last] != INF) return D[state][last];

    for(unsigned i = 0 ; i < father[last].size(); ++i) {

        if(state & (1 << father[last][i])) {//trecem din nodul last, in father[last][i], deci trebuie sa fim in nodul last

            if(father[last][i] == 0 && state != (1 << last) + 1) continue;
            //nodul 1 incheie ciclul, deci nu trecem prin el dacat la final

            D[state][last] = min(D[state][last], compute(state ^ (1 << last), father[last][i]) + cost[father[last][i]][last]);
        }
    }
    return D[state][last];
}

int main() {

    for(int i = 0; i <= N; ++i)
        for(int j = 0 ;j <= N; ++j)
            cost[i][j] = INF;

    read();

    int sol = INF;

    for(int i = 0 ;i < (1 << N); ++i)
        for(int j = 0 ;j < N; ++j)
            D[i][j] = INF;

    D[1][0] = 0;

    for(unsigned i = 0 ;i < father[0].size(); ++i)
        sol = min(sol, compute( (1 << N) - 1 ,  father[0][i] ) + cost[father[0][i]][0]);
    fout << sol << '\n';

    return 0;
}