#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
 vector <int> v[20];

 int n,m,dp[(1<<18)+3][20],cost[20][20],inf=2147000000,sol;
int main()
{ int i,j,t,x,y,b,nr;
    f>>n>>m;

    for(i=1;i<=m;i++)
    { f>>x>>y>>b;
        v[y].push_back(x);
        cost[x][y]=b;
    }
     nr=1<<n;

    for(i=0;i<nr;i++)
     for(j=0;j<n;j++)
      dp[i][j]=inf;

    for(i=0;i<n;i++)
     dp[1<<i][i]=0;


    for(i=0;i<nr;i++)
     for(j=0;j<n;j++)
      if ((i&(1<<j)))
       {
          for(t=0;t<v[j].size();t++)
           if (i&(1<<v[j][t]))
            dp[i][j]=min(dp[i][j],dp[i-(1<<j)][v[j][t]]+cost[v[j][t]][j]);
       }
     sol=inf;

    for(t=0;t<v[0].size();t++)
     sol=min(sol,dp[nr-1][v[0][t]]+cost[v[0][t]][0]);


     g<<sol;
    return 0;
}