#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define INF (~(1<<31))/2
#define MAX 20
typedef vector <pair<int, int> > :: iterator iter;
vector <pair <int, int> > Gt[MAX];
int a[1<<MAX][MAX];
int main()
{
    int n, j, ni, m, x, y, c, i, bestsol;
    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y >> c;
        Gt[y].push_back(make_pair(x, c));
    }
    for(i = 1 ; i < (1<<n) ; i++)
    {
        if(i == 1)
            continue;
        for(j = 0 ; (1<<j) <= i ; j++)
        {
            a[i][j] = INF;
            if(i & (1<<j))
            {
                ni = i - (1 << j);
                for(iter it = Gt[j].begin() ; it != Gt[j].end() ; it++)
                {
                    if(ni & (1<<(it->first)))
                    {
                        a[i][j] = min(a[i][j], a[ni][it->first] + it->second);
                    }
                }
            }
         //   cout << i << " " << j << " " << a[i][j] << "\n";
        }
    }
    bestsol = INF;
    for(iter it = Gt[0].begin() ; it != Gt[0].end() ; it++)
    {
        bestsol = min(bestsol, a[(1<<n) - 1][it->first] + it->second);
    }
    fout << bestsol << "\n";
}