#include <iostream>
#include <fstream>
#include <vector>

#define Infinit 100000005

using namespace std;

vector <int> G[20];
int N, S=Infinit, Best[1000000][20], Cost[20][20];

void Read ()
{
    ifstream fin ("hamilton.in");
    int M, X, Y, Z;
    fin >> N >> M;
    for (int i=0; i<N; ++i)
    {
        for (int j=0; j<N; ++j)
        {
            Cost[i][j]=Infinit;
        }
    }
    for (; M>0; --M)
    {
        fin >> X >> Y;
        fin >> Cost[X][Y];
        G[Y].push_back (X);
    }
    fin.close ();
}

void Type ()
{
    ofstream fout ("hamilton.out");
    fout << S << "\n";
    fout.close ();
}

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

void DetStare (int n, int Stare[])
{
    int i=0;
    while (n>0)
    {
        Stare[i++]=n%2;
        n/=2;
    }
    while (i<N)
    {
        Stare[i++]=0;
    }
}

int DetStare (int Stare[])
{
    int n=0, i=0;
    for (i=0; i<N; ++i)
    {
        n+=(Stare[i]*(1<<i));
    }
    return n;
}

int main()
{
    int Stare[20];
    Read ();
    for (int i=0; i<(1<<N); ++i)
    {
        for (int j=0; j<N; ++j)
        {
            Best[i][j]=Infinit;
        }
    }
    Best[1][0]=0;
    for (int i=0; i<(1<<N); ++i)
    {
        DetStare (i, Stare);
        for (int j=0; j<N; ++j)
        {
            if (Stare[j]==1)
            {
                Stare[j]=0;
                for (unsigned k=0; k<G[j].size (); ++k)
                {
                    if (Stare[G[j][k]]==1)
                    {
                        Best[i][j]=Min (Best[i][j], Best[DetStare (Stare)][G[j][k]]+Cost[G[j][k]][j]);
                    }
                }
                Stare[j]=1;
            }
        }
    }
    for (unsigned i=0; i<G[0].size (); ++i)
    {
        S=Min (S, Best[(1<<N)-1][G[0][i]]+Cost[G[0][i]][0]);
    }
    Type ();
    return 0;
}