#include <bits/stdc++.h>
#define INF 280000000

int mat[19][19], d[265000][19];

int minim(int a, int b){
    if(a<b)
        return a;
    return b;
}

int main()
{
    FILE *fin, *fout;
    int n, m, i, j, ii, x, y, c, k, mini;
    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++)
            if(i!=j)
                mat[i][j]=INF;
    for(i=0;i<m;i++){
        fscanf(fin, "%d%d%d", &x, &y, &c);
        mat[x][y]=c;
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            d[i][j]=INF;
    d[1][0]=0;
    for(i=3;i<(1<<n);i+=2)
        for(j=0;j<n;j++){
            ii=i^(1<<j);
            for(k=0;k<n;k++)
                if((1 << k)&ii && k!= j)
                    d[i][j]=minim(d[i][j], d[ii][k]+mat[k][j]);
        }
    mini=INF;
    for(i=0;i<n;i++)
        if(mini>d[(1<<n)-1][i]+mat[i][0])
            mini=d[(1<<n)-1][i]+mat[i][0];
    fprintf(fout, "%d", mini);
    fclose(fin);
    fclose(fout);

    return 0;
}