#include <bits/stdc++.h>
#define Dmax 20
#define inf 0x3F3F3F3F
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,Cost[Dmax][Dmax],C[1<<18][Dmax];

int main()
{
    f>>n>>m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            Cost[i][j] = inf;
    for(int i = 1; i < 1<<n; i++)
        for(int j = 0; j < n; j++)
            C[i][j] = inf;
    C[1][0] = 0;
    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        Cost[x][y] = z;
    }
    int lim = 1<<n;
    for(int mask = 1; mask < lim; mask++)
        for(int j = 0; j < n; j++)
            if((mask & (1<<j))&&(C[mask][j]!=inf))
                for(int k = 0; k < n; k++)
                    if((!(mask & (1<<k)))&&(Cost[j][k]!=inf))
                    {
                        int newMask = mask|(1<<k);
                        C[newMask][k] = min(C[newMask][k], C[mask][j] + Cost[j][k]);
                    }
   int sol = inf;
    for(int i = 0; i < n; i++)
        if(Cost[i][0]!=inf)
            sol = min(sol, C[(1<<n)-1][i] + Cost[i][0]);
    g<<sol;

    return 0;
}