#include <iostream>
#include <vector>

#define Inf 2000000000
#define NMax 20

using namespace std;

vector <int> G[NMax];
int N, S=Inf, Best[(1<<NMax)][NMax], Cost[NMax][NMax];

void Read ()
{
    freopen ("hamilton.in", "r", stdin);
    int M;
    scanf ("%d %d", &N, &M);
    for (; M>0; --M)
    {
        int X, Y, Z;
        scanf ("%d %d %d", &X, &Y, &Z);
        G[Y].push_back (X);
        Cost[X][Y]=Z;
    }
}

void Print ()
{
    freopen ("hamilton.out", "w", stdout);
    printf ("%d\n", S);
}

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

int Memo (int Conf, int X)
{
    if (Best[Conf][X]!=-1)
    {
        return Best[Conf][X];
    }
    Best[Conf][X]=Inf;
    for (int i=0; i<G[X].size (); ++i)
    {
        int V=G[X][i];
        int C=Cost[V][X];
        if (Conf&(1<<V))
        {
            Best[Conf][X]=Min (Best[Conf][X], Memo (Conf^(1<<X), V)+C);
        }
    }
    return Best[Conf][X];
}

int main()
{
    Read ();
    int n=(1<<N);
    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<N; ++j)
        {
            Best[i][j]=-1;
        }
    }
    Best[1][0]=0;
    for (int i=0; i<G[0].size (); ++i)
    {
        int V=G[0][i];
        S=Min (S, Cost[V][0]+Memo (n-1, V));
    }
    Print ();
    return 0;
}