#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int NMax = 18;
const int ConfMax = 1<<18;
const int oo = 2000000000;
vector <pair <int, int> > G[NMax + 50];
vector <pair <int, int> > GT[NMax + 50];
int DP[ConfMax + 5][NMax + 5];
int N,M;
void Read()
{
    fin >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        int x,y,c;
        fin >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
        GT[y].push_back(make_pair(x,c));
    }
}
void Solve()
{
    for(int Conf = 0; Conf <= ConfMax; ++Conf)
        for(int  i = 0; i <= N; ++i)
            DP[Conf][i] = oo;
    DP[1][0] = 0;
    for(int Conf = 0; Conf < (1<<N); ++Conf)
    {
        for(int i = 0; i < N; ++i)
            if(Conf & (1<<i))
            {
                int OldConf = Conf - (1<<i);
                for(auto j : GT[i])
                {
                    int Nod = j.first, Value = j.second;
                    if(OldConf & (1<<Nod))
                        DP[Conf][i] = min(DP[Conf][i],DP[OldConf][Nod] + Value);
                }
            }
    }
}
void Print()
{
    int Sol = oo;
    for(auto i : GT[0])
    {
        int Nod = i.first, Value = i.second;
        Sol = min(Sol,DP[(1<<N)-1][Nod] + Value);
    }
    fout << Sol << "\n";
}
int main()
{
    Read();
    Solve();
    Print();
}