#include <iostream>
#include <fstream>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int dim = 19;
const int INF = 1e9;
const int maxm = (1<<18);

int a[dim][dim],n,m,dp[maxm][dim];

int main()
{
    in >> n >> m;
    for (int i=0; i<=n; i++)
    {
        for (int j=0; j<=n; j++)
        {
            a[i][j] = INF;
        }
    }
    for (int i=1,x,y,c; i<=m; i++)
    {
        in >> x >> y >> c;
        a[x][y] = c;
    }
    for (int i=1; i<=maxm-1; i++)
    {
        for (int j=0; j<n; j++)
        {
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
    for (int i=3; i<=(1<<n) - 1; i += 2)
    {
        for (int j=0; j<n; j++)
        {
            if ((i&(1<<j)) != 0)
            {
                int acm = (i^(1<<j));
                for (int p=0; p<n; p++)
                {
                    if ((acm&(1<<p)) != 0)
                    {
                        dp[i][j] = min(dp[i][j], dp[acm][p] + a[p][j]);
                    }
                }
            }
        }
    }
    int mini = INF;
    for (int i=0; i<n; i++)
    {
        mini = min(mini, dp[((1<<n)-1)][i] + a[i][0]);
    }
    out << mini;
    return 0;
}