#include <fstream>
#include <cstring>
#define NM 20
#define DM 269944
#define INF 0x7fffffff

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int N,M,i,j,k,a,b,c,S=1,NP;
int C[NM][NM];
int D[NM][DM];
int PW[NM];
int ANS=INF;

int main ()
{
    for (i=0; i<NM; i++)
        for (j=0; j<NM; j++)
            C[i][j]=INF;

    f >> N >> M;
    for (i=1; i<=M; i++)
    {
        f >> a >> b >> c;
        C[a][b]=c;
    }

    for (PW[0]=1,i=1; i<NM; i++)
        PW[i]=2*PW[i-1];

    for (i=0; i<NM; i++)
        for (j=0; j<DM; j++)
            D[i][j]=INF;

    D[0][1]=0;

    NP=PW[N];
    for (i=1; i<NP-1; i++)
        for (j=0; j<N; j++)
            if ((i&PW[j]) && D[j][i]!=INF)
                for (k=0; k<N; k++)
                    if ((i&PW[k])==0 && C[j][k]!=INF)
                        D[k][i|PW[k]]=min(D[k][i|PW[k]],D[j][i]+C[j][k]);

    for (i=1; i<N; i++)
        if (C[i][0]!=INF && D[i][NP-1]!=INF)
            ANS=min(ANS,D[i][NP-1]+C[i][0]);

    g << ANS << '\n';
    f.close();
    g.close();
    return 0;
}