#include <bits/stdc++.h>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int PMAX=(1<<19);
const short NMAX=19;
const int inf=1000000000;
int n,m,dp[NMAX][PMAX],M[NMAX][NMAX];
///dp[i][j]-costul minim de la nodul 0 la nodul i trecand prin j valori
///binare(j fiind maxim 18)
vector<int>L[NMAX];
queue<pair<int,int> >C;
inline void READ()
{
    fin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            M[i][j]=inf;
    for(int i=1;i<=m;i++)
    {
        int nod,nod1,cost;
        fin>>nod>>nod1>>cost;
        L[nod].push_back(nod1);
        M[nod][nod1]=cost;
    }
}
inline void DP_SOLVE()
{
    int bit,sol;
    bit=(1<<n)-1;
    for(int i=0;i<n;i++)
        for(int j=0;j<=bit;j++)
            dp[i][j]=inf;
    dp[0][1]=0;
    C.push({0,1});
    ///1- are bitul 0=1
    while(!C.empty())
    {
        int x=C.front().first;
        int y=C.front().second;
        C.pop();
        int lug=L[x].size();
        for(int pas=0;pas<lug;pas++)
        {
            int i=L[x][pas];
            if((y&(1<<i))==0) ///verific daca bitul i al lui y este 0
            {
                int stare;
                stare=(y|(1<<i));
                ///trec la numarul care are bitul i=1
                if(dp[i][stare]>dp[x][y]+M[x][i])
                {
                    dp[i][stare]=dp[x][y]+M[x][i];
                    C.push({i,stare});
                }
            }
        }
    }
    sol=inf;
    for(int i=1;i<n;i++)
        sol=min(sol,dp[i][bit]+M[i][0]);
        ///bit are n biti de 1,inseamna ca am trecut prin cele n noduri
    fout<<sol<<"\n";
}
int main()
{
    READ();
    DP_SOLVE();
    fin.close();
    fout.close();
    return 0;
}