#include <fstream>
#include <vector>
#define NMax 20
#define oo 1000000000
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

vector <int> G[NMax];
int N,M,C[NMax][NMax],DP[262150][NMax];

void Read()
{
    fin>>N>>M;

    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            C[i][j]=oo;

    for(int i=1;i<=M;i++)
        {
            int x,y,c;
            fin>>x>>y>>c;
            G[y].push_back(x);
            C[x][y]=c;
        }
}

void Solve()
{
    for(int i=1;i<(1<<N);i++)
        for(int j=0;j<N;j++)
            DP[i][j]=oo;
    DP[1][0]=0;

  for(int conf=1;conf<(1<<N);conf++)
        for(int i=0;i<N;i++)
            {
                if(conf & (1<<i))
                    for(unsigned int j=0;j<G[i].size();j++)
                        {
                            int Vecin=G[i][j];
                           if(conf & (1<<Vecin))
                            DP[conf][i]=min(DP[conf][i],DP[conf^(1<<i)][Vecin]+C[Vecin][i]);
                        }
            }
}

void Print()
{
    int Sol=oo;
    for(unsigned int i=0;i<G[0].size();i++)
        {
            int Vecin=G[0][i];
            Sol=min(Sol,DP[(1<<N)-1][Vecin]+C[Vecin][0]);
        }
    fout<<Sol<<"\n";
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}