#include <cstdio>
#include <vector>
#include <algorithm>
#define INF 2000000000
using namespace std;
vector <pair <int,int> > v[20];
int d[300000][20];
int main()
{
    FILE *fin = fopen ("hamilton.in","r");
    FILE *fout = fopen ("hamilton.out","w");
    int n,m,i,j,k,vecin,x,y,cst,sol;
    fscanf (fin,"%d%d",&n,&m);
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&cst);
        v[y].push_back( make_pair (x,cst));
    }
    // d[i][j] = costul minim daca pana la nodul i am configuratia j
    // incepem cu nodul 1
    for (i=0;i<n;i++){
        for (j=0;j<=(1<<n);j++)
            d[j][i]=INF;
    }
    d[1][0]=0;
    for (i=0;i<(1<<n);i++){
        for (j=0;j<n;j++){
           // if (i==9 && j==3)
             //   printf ("a");
            if (i & (1<<j)){ // j e inclus in i
                for (k=0;k<v[j].size();k++){
                    vecin=v[j][k].first;
                    if (i & (1<<vecin))
                        d[i][j]=min (d[i][j], d[i-(1<<j)][vecin]+v[j][k].second);
                }
            }
        }
    }
    sol=INF;
    for (i=0;i<v[0].size();i++){
        vecin=v[0][i].first;
        sol=min(sol,d[(1<<n)-1][vecin]+v[0][i].second);
    }
    fprintf (fout,"%d",sol);
    return 0;
}