#include <bits/stdc++.h>
#define NMAX 20
#define INF 999999999
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int cost[NMAX][NMAX];
vector<int> a[NMAX];
int n,m;
int sol[1<<NMAX][NMAX];
void citire();
int main()
{citire();

    return 0;
}
void citire()
{int x,y;
 int i,j;
    fin>>n>>m;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
           cost[i][j]=INF;

    for(i=1;i<=m;i++)
        {
        fin>>x>>y;
        a[y].push_back(x); ///in y pot ajunge din x
        fin>>cost[x][y];
        }
     for(i=0;i< (1<<n);i++)
       for(j=0;j<n;j++)
           sol[i][j]=INF;
    sol[1][0]=0; ///aici ma aflu
    for(i=0;i< (1<<n);i++)
        for(j=0; j<n;j++)
            if( (1<<j) & i )
                {
                 ///daca pot compune drumul
                 for(int ct=0; ct< a[j].size();ct++)
                    {
                     int act=a[j][ct];
                     if( i && (1<<act) )
                        {
                         sol[i][j]= min(sol[i][j],sol[i ^ (1<<j)][act] + cost[act][j]    );

                        }
                    }
                }
     int minim=INF;
     for(i=0;i<a[0].size();i++)
            {
             minim= min( minim, sol[ (1<<n)-1  ][ a[0][i]]+ cost[a[0][i]  ][0]   );
            }
       fout<<minim;
}