#include <stdio.h>
using namespace std;
FILE *fin = fopen("hamilton.in" ,"r");
FILE *fout = fopen("hamilton.out", "w");
#define INF 1000000000
int este(int i, int j)
{
    if(i & (1<<j) !=0) return 1;
    return 0;
}
int cost[20][20];
int best[ 140000 ][20];
int main()
{
    int n,m;
    fscanf(fin, "%d%d", &n, &m);
    for(int i=0; i < n;i++)
        for(int j=1;j < 1<<n ;j++)
    {
        best[j][i]=INF;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        fscanf(fin, "%d%d%d", &x, &y, &z);
       // best[1<<x + 1<<y][y] = z;
        cost[x][y] = z;
    }
    for(int i=0;i<n;i++) best[(1<<i)][i]=0;
    best[1][0]=0;
    for(int j=1;j < 1<<n ;j++)
    {
        for(int k=0;k<n;k++)
        {
            if(este(j,k)==1)
            {
                for(int q=0;q<n;q++)
                {
                    if(este(j,q)==1 && cost[q][k]!=0 && q!=k)
                    {
                        if(best[j][k] > best[j^(1<<k)][q] + cost[q][k]) best[j][k] = best[j^(1<<k)][q] + cost[q][k];
                    }
                }
            }
        }
    }
    int minim = 10000000;
    for(int i=1;i<n;i++)
    {
            if(cost[i][0]!=0 )
            {
                if(best[ (1<<n) - 1][i] + cost[i][0] < minim) minim = best[ (1<<n) - 1][i] + cost[i][0];
            }
    }
    fprintf(fout, "%d", minim);
    return 0;
}