#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 18;
const int MASK = 1<<18;
int n,m;
vector <pair<int,int>> l[NMAX];
int dp[NMAX][MASK];
int rasp = 1e9;

int main()
{
    int x,y,c;
    fin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        fin>>x>>y>>c;
        l[y].push_back({x,c});
    }
    for(int i = 0; i < n; i++)
        for(int mask = 0; mask < 1<<n; mask++)
            dp[i][mask] = 1e9;
    dp[0][1]=0;
    for(int mask = 0; mask < 1<<n; mask++)
        for(int j = 0; j < n; j++)
            if((mask&(1<<j)) != 0)
                for(auto e:l[j])
                    if((mask&(1<<e.first))!=0)
                        dp[j][mask]=min(dp[j][mask],dp[e.first][(mask^(1<<j))]+e.second);
    int mask = (1<<n)-1;
    for(auto e:l[0])
        rasp = min(rasp,dp[e.first][mask]+e.second);
    fout << rasp;
    return 0;
}