#include <bits/stdc++.h>

using namespace std;

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

int n,m,v[200][200],rez[1<<20][200], INF = 1<<30, primul[1<<20][20];

int main()
{
    in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,pret;
        in>>x>>y>>pret;
        v[x][y] = pret;
       // if(x == 0)
         //   rez[(1<<y)^1][y] = pret;
    }
   // for(int j = 0;j < n;j++)
    {
       // for(int i = 0;i < n;i++)
         //   cout<<v[i][j]<<" ";
        //cout<<"\n";
    }
    for(int i = 0;i < 1<<n;i++)
    {
        for(int j = 0;j < n;j++)
            rez[i][j] = 20000000;
    }
  //  for(int i = 0;i < n;i++)
      //  if(v[i][0])
       //     rez[(1<<i)^1][i] = v[i][0];
     rez[1<<0][0] = 0;
   /* for(int j = 0;j < n;j++)
    {
        for(int i = 1;i < 1<<n;i++)
            cout<<rez[i][j]<<" ";
        cout<<"\n";
    }*/
    for(int mask = 1;mask < 1<<n;mask++)
    {
        for(int last = 0;last < n;last++)
        {
            if(mask&(1<<last) != 0)
            {
                for(int x = 0;x < n;x++)
                {
                    if(v[x][last] && mask&(1<<x) != 0 && x != last)
                    {
                        int nr = mask^(1<<last);   //100101100
                       // if(rez[nr][x] + v[x][last] < rez[mask][last])
                         //   primul[mask][last] = primul[nr][x];
                        rez[mask][last] = min(rez[nr][x] + v[x][last], rez[mask][last]);
                    }
                }
            }
    //    if(mask == (1<<n)-1 && v[last][0])
        //    rez[mask][last] += v[last][0];
        }
       /* for(int i = 0;i < n;i++)
        {
            int cm = mask,numar = 0,p = 1;
            while(cm)
            {
                numar = numar+cm%2*p;
                cm /= 2;
                p *= 10;
            }
            out<<numar<<" "<<i<<" "<<rez[mask][i]<<"\n";
        }*/
    }
    int mx = 1000000;
  //  for(int i = 1;i < n;i++)
    //{
      //  cout<<rez[(1<<n) -1][i]<<" ";
   // }
   // out<<rez[(1<<n) -1][n-1]<<"\n";
    for(int i = 1;i < n;i++)
    {
      //  if(v[0][primul[(1<<n) -1][i]] && v[i][0])
            if(rez[(1<<n) -1][i] + v[i][0] < mx && rez[(1<<n) -1][i] && v[i][0])
                mx = rez[(1<<n) -1][i] + v[i][0];

      //  if(rez[(1<<n) -1][i] < mx && rez[(1<<n) -1][i])
         //  mx = rez[(1<<n) -1][i];
    }
    out<<mx;

    return 0;
}