#include <vector>
#include <fstream>
#define mcon 262146
#define pb(x) push_back(x)
using namespace std;
vector<int> v[20];
int cost[20][20],c[mcon][20],n,m,x,y,z,rez=1<<30;
int chcm(int conf,int last)
{
    if(c[conf][last]==1000000000)
    {for(int i=0;i<v[last].size();i++)
      if(conf&(1<<v[last][i]))                           
       {
       if(conf==(1<<last)+1||v[last][i]!=0)
       c[conf][last]=min(c[conf][last],chcm(conf^(1<<last),v[last][i])+cost[v[last][i]][last]);
       }                          
                                 
                                 }
    return c[conf][last];
    }

int main ()
{int i,j;
    ifstream f("hamilton.in");
 ofstream g("hamilton.out");
f>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cost[i][j]=1000000000;
while(m)
{f>>x>>y>>z;
v[y].pb(x);
cost[x][y]=z;        
 m--;     }
for(i=0;i<mcon;i++)
for(j=0;j<n;j++)
{c[i][j]=1000000000;
}
c[1][0]=0;
for(i=0;i<v[0].size();i++)
rez=min(rez,chcm((1<<n)-1,v[0][i])+cost[v[0][i]][0]);
g<<rez;
 f.close(); g.close();
return 0;
}