#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m;
vector<pair<int,int>> v[22];
int main()
{
    fin>>n>>m;
    int x,y,c;
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    vector<vector<int>> dp(1<<n,vector<int>(n,1e9));
    dp[1][0]=0;
    for(int mask=3; mask<1<<n; mask+=2)
    {
        for(int bit=1; bit<n; bit++)
        {
            if((1<<bit)&mask)
            {
                for(auto x:v[bit])
                {
                    if((1<<x.first)&mask)
                        dp[mask][bit]=min(dp[mask][bit],dp[mask^(1<<bit)][x.first]+x.second);
                }
            }
        }
    }
    int minim=1e9;
    for(auto x:v[0])
        minim=min(minim,dp[(1<<n)-1][x.first]+x.second);
    fout<<minim;
    return 0;
}