#include <fstream>
#include <vector>
#define DIM 18
#define INF 100000000

using namespace std;

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

vector< pair<int, int> > L[DIM];
vector< pair<int, int> > K[DIM];
int D[1<<DIM][DIM];

int n, m, c, x, y, i, minim, j;

void rec(int stare, int nod) {
    // D[stare][nod] = costul minim sa vizitez toate nodurile din stare
    // si ultimul sa fie nod

    if (!(stare & (1<<nod)))
        return;

    if (D[stare][nod]!=INF)
        return;

    if (stare == 1)
        return;

    //caut muchie [x nod] si ma intereseaza [stare fara nod][x]

    for (int i=0;i<K[nod].size();i++) {
        int x = K[nod][i].first;
        if (!(stare & (1<<x)))
            continue;
        rec(stare-(1<<nod), x);
        if (D[stare][nod] > D[stare-(1<<nod)][x] + K[nod][i].second)
            D[stare][nod] = D[stare-(1<<nod)][x] + K[nod][i].second;
    }
}

int main(){
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        //L[x].push_back( make_pair(y,c) );
        K[y].push_back( make_pair(x,c) );
    }

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

    D[1][0] = 0;

    minim = INF;

    for (i=0;i<K[0].size();i++) {
        rec((1<<n)-1, K[0][i].first);
        if (minim > D[(1<<n)-1][K[0][i].first] + K[0][i].second)
            minim = D[(1<<n)-1][K[0][i].first] + K[0][i].second;
    }

    fout<<minim;
    return 0;
}