///Alexandru Morus
#include <bits/stdc++.h>

using namespace std;

ifstream  in("hamilton.in");
ofstream out ("hamilton.out");
int mt[260001][69];
vector <pair <int, int>> g[100001];
int vf[260001];
int main ()
{
    int i,n,m,a,b,c,masca,afs,j;
    in >> n >> m;
    for(i = 1; i < (1 << n); i ++)
    {
        for(j = 0; j <= n; j ++)
        {
            mt[i][j] = 99999999;
        }
    }
    for(i = 1; i <= m; i ++)
    {
        in >> a >> b >> c;
        g[b].push_back(make_pair(a,c));
        if(b == 0)
        {
            vf[a] = c;
        }
    }
    mt[1][0] = 0;
    for(masca = 3; masca < (1 << n); masca += 2)
    {
        for(i = 1; i < n; i ++)
        {
            if(masca & (1 << i))
            {
                for(auto j : g[i])
                {
                    mt[masca][i] = min(mt[masca][i],mt[masca ^ (1 << i)][j.first] + j.second);
                }
            }
        }
    }
    afs = 99999999;
    for(i = 0; i < n; i ++)
    {
        if(vf[i])
        {
            afs = min(afs, mt[(1 << n) - 1][i] + vf[i]);
        }
    }
    out << afs;
    return 0;
}