#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 19
#define MAX2 262150
#define INF 1e7
using namespace std;

vector <int> A[NMAX];
int Cost[NMAX][NMAX];
int C[MAX2][NMAX];

int main()
{
    FILE *fin, *fout;
    int n,m,i,j,k,sol,x,y,c;
    fin = fopen("hamilton.in","r");
    fout = fopen("hamilton.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            Cost[i][j] = INF;
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d %d",&x,&y,&c);
        Cost[x][y] = c;
        A[y].push_back(x);
    }
    for(i=0; i < (1<<n);i++)
        for(j=0;j<n;j++)
            C[i][j] = INF;
    C[1][0] = 0;
    for(i=0;i < (1<<n);i++)
        for(j=0;j<n;j++)
            if(i & (1<<j))
                for(k=0;k<A[j].size();k++)
                    if(i & (1<<A[j][k]))
                        C[i][j] = min(C[i][j], C[i ^ (1<<j)][A[j][k]] + Cost[A[j][k]][j]);

    sol = INF;
    for(i=0;i<A[0].size();i++)
        sol = min(sol, C[(1<<n) - 1][A[0][i]] + Cost[A[0][i]][0]);
    fprintf(fout,"%d\n",sol);
    fclose(fin);
    fclose(fout);
    return 0;
}