#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>
#define NMAX 262144
using namespace std;

int n,m;
long long int dp[NMAX+3][19];

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

unordered_map<int,long long int>  graf[19];//graful de costuri

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        long long int cost;
        fin>>x>>y>>cost;
       
        graf[x].insert({y,cost});
    }
    //ar fi bine sa pun INT_MAX peste tot in dp
    for(int cod=1; cod<( 1<<n ); cod+=2)
    {
        for(int last=0; last<n; last++)
        {
            dp[cod][last]=INT_MAX;
        }
    }

    dp[1][0]=0;
    for(int cod=1; cod<( 1<<n ); cod+=2)
    {
        for(int last=0; last<n; last++)
        {
            if(((cod>>last) & 1)==1)
            {
                //am elementul asta in cod
                for(auto elem:graf[last])
                {
                    int urm=elem.first;//am venit de aici
                    if(((cod>>urm)&1)==0)
                    {
                        // e prima data in codificarea asta cand dau in elem asta
                        int p2=(1<<urm);
                        dp[cod+p2][urm]=min(dp[cod+p2][urm],dp[cod][last]+elem.second);
                    }
                }
            }
        }
    }
    //imi iau minimul de la final
    long long int minim=INT_MAX;
    int p2=(1<<n)-1;
    for(int i=1; i<n; i++)
    {
        auto itr=graf[i].find(0);
        if(itr!=graf[i].end())
        {
            minim=min(minim,dp[p2][i]+itr->second);
        }
       
    }
    fout<<minim;
    return 0;
}