#include <bits/stdc++.h>

using namespace std;

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

int n,m,v[20][20],rez[1<<20][20], 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;
    }
   // for(int j = 0;j < n;j++)
   // {
    //    for(int i = 0;i < n;i++)
     //       cout<<v[i][j]<<" ";
      //  cout<<"\n";
   // }
    for(int i = 1;i < 1<<n;i++)
    {
        for(int j = 0;j < n;j++)
            rez[i][j] = 20000000;
    }
    for(int i = 0;i < n;i++)
        rez[1<<i][i] = 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])
                    {
                        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]);
                    }
                }
            }
        }
       // for(int j = 0;j < n;j++)
       // {
            //for(int i = 1;i < 1<<n;i++)
              //  cout<<rez[i][j]<<" ";
            //cout<<"\n";
       // }
    }
    int mx = 1000000;
    //for(int i = 0;i < n;i++)
   // {
        //cout<<rez[(1<<n) -1][i]<<" "<<v[i][primul[(1<<n) -1][i]]<<"\n";
    //}
   // out<<rez[(1<<n) -1][n-1]<<"\n";
    for(int i = 0;i < n;i++)
    {
        if(v[i][primul[(1<<n) -1][i]])
            if(rez[(1<<n) -1][i] + v[i][primul[(1<<n) -1][i]] < mx && rez[(1<<n) -1][i])
                mx = rez[(1<<n) -1][i] + v[i][primul[(1<<n) -1][i]];
    }
    out<<mx;

    return 0;
}