#include<fstream>
#include<vector>
#define NMAX 21
#define SIZE (1 << 18) + 5
#define INF 2000000000
using namespace std;
vector<pair<int, int> > G[NMAX];
int n, m, x, y, z, sol;
int n_stage;
int d[SIZE][NMAX], d_mch[NMAX][NMAX];
ifstream _cin("hamilton.in");
ofstream _cout("hamilton.out");

void init()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            d_mch[i][j] = INF;
        }
    }

    for(int stare = 0; stare < (1 << n); stare++)
    {
        for(int nod = 0; nod < n; nod++)
        {
            d[stare][nod] = INF;
        }
    }
    d[1][0] = 0;

    sol = INF;
}

void hamilton()
{
    for(int stare = 0; stare < (1 << n); stare++)
    {
        for(int nod = 0; nod < n; nod++)
        {
            if(d[stare][nod] != INF)
            {
                for(int i = 0; i < G[nod].size(); i++)
                {
                    int fiu = G[nod][i].first;
                    int dist = G[nod][i].second;
                    if((stare & (1 << fiu)) == 0)
                    {
                        n_stage = stare + (1 << fiu);
                        d[n_stage][fiu] = min(d[stare][nod] + dist, d[n_stage][fiu]);
                    }
                }
            }
        }
    }
}

void cicle_finish()
{
    for(int nod = 1; nod < n; nod++)
    {
        if(d[(1 << n) - 1][nod] != INF && d_mch[nod][0] != INF)
        {
            sol = min(sol, d[(1 << n) - 1][nod] + d_mch[nod][0]);
        }
    }
}

int main()
{
    _cin >> n >> m;

    init();

    for(int i = 1; i <= m; i++)
    {
        _cin >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
        d_mch[x][y] = z;
    }

    hamilton();

    cicle_finish();

    _cout << sol;
    return 0;
}