#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

#define NMAX 19
#define pb push_back

using namespace std;
int n, m, dp[1<<18][NMAX], x, y, cst, sze, mask, ans, lim;
const int inf = (1<<30)-1;
struct muchie
{
    int vec;
    int cost;
} tmp;
vector <muchie> g[NMAX], gt;

int main()
{
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i =  1; i<= m; ++i)
    {
        scanf("%d %d %d", &x, &y, &cst);
        ++x;++y;
        //printf("%d %d %d\n", x, y, cst);
        tmp.vec = y;
        tmp.cost = cst;
        g[x].pb(tmp);
        tmp.vec = x;
        if(y == 1) gt.push_back(tmp);
    }
    lim = (1<<n)-1;
    for(int i = 1; i<= lim; ++i)
    {
        for(int j = 1; j<= n; ++j)
        {
            dp[i][j] = inf;
        }
    }
    dp[1][1] = 0;
    for(int i = 1; i<= lim; ++i)
    {
        for(int j = 1; j<= n; ++j)
        {
            if(dp[i][j] >= inf) continue;
            //printf("i = %d j = %d dp[i][j] = %d\n", i, j, dp[i][j]);
            sze = g[j].size();
            for(int k = 0; k< sze; ++k)
            {
                mask = (1<<(g[j][k].vec - 1));
                if(i&mask) continue;
                //printf("update dp[%d][%d] cu %d\n", (i|mask), g[j][k].vec, g[j][k].cost + dp[i][j]);
                dp[(i|mask)][g[j][k].vec] = min(g[j][k].cost + dp[i][j], dp[(i|mask)][g[j][k].vec]);
            }
        }
    }
    sze = gt.size();
    ans = inf;
    //printf("%d \n", ans);
    for(int i = 0; i< sze; ++i)
    {
        //printf("option %d\n", dp[lim][gt[i].vec]);
        if(dp[lim][gt[i].vec] + gt[i].cost < ans) ans = dp[lim][gt[i].vec] + gt[i].cost;
    }
    printf("%d\n", ans);
    return 0;
}