#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
ifstream fi("hamilton.in");
ofstream fo("hamilton.out");
vector<int> V[19];
int C[19][19];
int M[262150][19];
int n,m;
int a,b,c;
int rez=0,i,j;
int calc(int s, int conf, int d)
{
    if(M[conf][d] == -1)
    {
        M[conf][d]=2000000000;
        for(int i=0;i<=V[d].size();i++)
            if(conf & (1<<V[d][i]))
            {
                if (V[d][i] == s && ((conf ^ (1<<d)) != (1<<s)))
                    continue;
                M[conf][d] = min(M[conf][d], calc(s, conf ^ (1<<d), V[d][i]) + C[V[d][i]][d]);
            }
    }
    return M[conf][d];
}
int main()
{
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>a>>b>>c;
        C[a][b]=c;
        V[b].push_back(a);
    }
    rez=2000000000;
    for(i=1;i<=n;i++)
    {
        memset(M,-1,sizeof(M));
        M[1<<i][i]=0;
        for(j=0;j<V[i].size();j++)
            rez=min(rez,calc(i,(1<<n)-1,V[i][j])+C[V[i][j]][i]);
    }
    fo<<rez;
    fi.close();
    fo.close();
    return 0;
}