#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 20
#define NMAX2 270000
#define pb push_back
#define MOD 2000000000
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
vector <int> v[NMAX];
queue <int> qnod;
bool viz[NMAX][20];
int n,m,pas,cost[20][20];
int d[NMAX2][NMAX];
void read()
{
    int a,b,c;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        v[b].pb(a);
        cost[a][b] = c;
    }
}
void solve()
{
    int y;
    for(int i=1;i< ( 1 << n);i+=2)
    {
        for(int j=0;j<n;j++)
        {
            if( i  & ( 1 << j))
            {
                for(int k=0;k<v[j].size();k++)
                {
                    y = v[j][k];
                    if((i & (1 << y)) != 0)
                    if(d[i^(1<<j)][y] + cost[y][j] < d[i][j] )
                        d[i][j] = cost[y][j] + d[i^(1<<j)][y];
                }
            }
        }
    }
}
void init()
{
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            d[i][j] = MOD;
    d[1][0] = 0;
}
int main()
{
    read();
    init();
    solve();
   /* for(int i=1;i<(1<<n);i++)
    {
        for(int j=0;j<n;j++)
            fout<<d[i][j]<<" ";
        fout<<"\n";
    }*/
    int r= 999999999,pow = (1<<n);
    pow--;
    for(int i=0;i<v[0].size();i++)
        if(r>d[pow][v[0][i]] + cost[v[0][i]][0])
            r=d[pow][v[0][i]] + cost[v[0][i]][0];
//        if(r > d[pow][i] + cost[i][1])
       //     r =  d[pow][i] + cost[i][1];
    fout<<r;
}