#include <iostream>
#include <fstream>
#include <vector>
#define Mmask 1048576
#define Nmax 25
using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int dp[Mmask][Nmax],x, y, n, m, c, cst[Nmax][Nmax], rsp, tata[Nmax],sum;
vector<pair<int,int> >v[Nmax];
const int inf = 1 << 30;
int calc(int mask, int nod)
{
    if(mask == 0) tata[nod] = nod;
    if(dp[mask][nod] != inf)return dp[mask][nod];
    for(int i = 0 ; i < n; i++)
        if((mask & (1 << i)) && cst[i][nod])
                {
                    int nr = calc(mask - (1 << i), i) + cst[i][nod];
                    if(nod == 0 && nr + cst[0][tata[i]] < dp[mask][nod])
                    {
                        dp[mask][nod] = nr + cst[0][tata[i]];
                        tata[nod] = tata[i];
                    }
                    else if(nod != 0 && nr < dp[mask][nod])
                    {
                        dp[mask][nod] = nr;
                        tata[nod] = tata[i];
                    }
                }
    return dp[mask][nod];
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        fin >> cst[x][y];
    }
    for(int i = 1; i <= (1 << n) - 1; i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = inf;
    for(int i = 0 ; i < n; i++)
        dp[0][i] = 0;
    sum = calc( ((1 << n) - 1) - 1, 0);
    fout << sum;
    return 0;
}