#include <bits/stdc++.h>

using namespace std;

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

int n,m,v[20][20],rez[1<<20][20],INF = 1<<20;

int main()
{
    in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,cost;
        in>>x>>y>>cost;
        v[x][y] = cost;
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j <= 1<<n;j++)
            rez[j][i] = INF;
    }
    rez[1][0] = 0;
    for(int mask = 1;mask < 1<<n;mask++)
    {
        for(int last = 0;last < n;last++)
        {
            if((mask & (1<<last)) != 0)
            {
                for(int x = 0;x < n;x++)
                {
                    if((mask & (1<<x)) == 0 && v[last][x])
                    {
                        int nr = mask^(1<<x);
                        rez[nr][x] = min(rez[nr][x], rez[mask][last] + v[last][x]);
                    }
                }
            }
        }
    }
    int mx = INF;
    for(int i = 1;i < n;i++)
    {
        if(v[i][0])
            mx = min(mx, rez[(1<<n)-1][i] + v[i][0]);
    }
    out<<mx;

    return 0;
}