#include<fstream>
#define CONF_MAX 262154
#define NMAX 20
#define INF 200000010

using namespace std;

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

int n, m, LIM=1, best[CONF_MAX][NMAX], a[NMAX][NMAX];

void Citeste()
{
    int i, j,  x, y, c;

    f>>n>>m;

    for (i=0; i<=n; ++i)
        for (j=0; j<=n; ++j)
            a[i][j]=INF;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        a[x][y]=c;/*=a[y][x]=c;*/
    }
}

void Initializeaza()
{
    int i, j;

   LIM=1<<n;

    for (i=0; i<LIM; ++i)
        for (j=0; j<n; ++j)
            best[i][j]=INF;
    best[1][0]=0;
}

int Calculeaza(int conf, int nod)
{
    int i, sol=INF;

    for (i=0; i<n; ++i)
        if (conf&(1<<i)!=0 && a[i][nod]!=INF)
            sol=min(sol, best[conf][i]+a[i][nod]);

    return sol;
}

void Solve()
{
    int conf, i, REZ=INF;

    for (conf=2; conf<LIM; ++conf)
        for (i=0; i<n; ++i)
            if (conf&(1<<i)!=0)
                best[conf][i]=Calculeaza(conf^(1<<i), i);

    LIM--;

    for (i=0; i<n; ++i)
        if (a[i][1]!=INF) REZ=min(REZ, a[i][1]+best[LIM][i]);

    g<<REZ<<"\n";
}

int main()
{
    Citeste();

    Initializeaza();

    Solve();

    f.close();
    g.close();

    return 0;
}