#include<fstream>
using namespace std;
const int MAXN=20;
const int MAXE=(1<<20);
const int INF=(1<<30)-1;
int n,m,SOL;
int C[MAXN][MAXE][MAXN];
int G[MAXN][MAXN];
void read()
{
    ifstream fin("hamilton.in");
    fin>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int x,y,z;
        fin>>x>>y>>z;
        G[x][y]=z;
    }
    fin.close();
}
void write()
{
    ofstream fout("hamilton.out");
    fout<<SOL<<'\n';
    fout.close();
}
void init()
{
    int i,j,k;
    for (i=0; i<n; ++i)
        for (j=0; j<(1<<n); ++j)
            for (k=0; k<n; ++k)
                C[i][j][k]=INF;
}
int solve()
{
    init();
    int i,j,k,v;
    //CAZ DE BAZA
    for (i=0; i<n; ++i)
        C[i][1<<i][i]=0;

    //RELATIA DE RECURENTA
    for (i=0; i<n; ++i)
        for (j=0; j<(1<<n); ++j)
            for (k=0; k<n; ++k)
                for (v=0; v<n; ++v)
                    if (j&(1<<v) && G[v][k])
                        C[i][j][k]=min(C[i][j][k], C[i][j ^ (1<<k)][v] + G[v][k]);

    SOL=INF;
    for (i=0; i<n; ++i)
        for (k=0; k<n; ++k)
            if (SOL>C[i][(1<<n)-1][k]+G[k][i] && G[k][i])
                SOL=C[i][(1<<n)-1][k]+G[k][i];


}
int main()
{
    read();
    solve();
    write();
    return 0;
}