///CICLU HAMILTONIAN
#include <iostream>
#include <fstream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();
typedef vector<int>::iterator VIT;

int main() {
    ifstream inStr("hamilton.in");
    ofstream outStr("hamilton.out");

    int N, M;
    inStr >> N >> M;

    vector<vector<int> > adjList(N);
    vector<vector<int> > cost(N, vector<int>(N));

    int from, to;
    for(int i=0; i<M; ++i) {
        inStr >> from >> to;
        inStr >> cost[from][to];
        adjList[to].push_back(from);
    }

    vector<vector<int> > C((1<<N), vector<int>(N, INF));
    C[1][0] = 0;

    int curr_b;
    for(int conf = 1; conf<=(1<<N)-1; ++conf)
        if(conf & 1)
            for(int j=0; j<N; ++j)
                if(conf & (1<<(j)) == 1<<(j))
                    for(VIT v = adjList[j].begin(); v != adjList[j].end(); ++v) {
                        curr_b = 1<<*v;
                        if(conf & curr_b == curr_b && C[conf ^ (1<<j)][*v] != INF)
                            C[conf][j] = min(C[conf][j], C[conf ^ (1<<j)][*v] + cost[*v][j]);
                    }

    for(VIT it = adjList[0].begin(); it != adjList[0].end(); ++it)
        C[(1<<N)-1][0] = min(C[(1<<N)-1][0], C[(1<<N)-1][*it] + cost[*it][0]);

    outStr << C[(1<<N)-1][0];

    return 0;
}