#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,c[20][20],dp[(1<<18)+5][18];
vector <int> v[20];

void Solve()
{ int i,j,t,nod,ok=dp[0][0],sol=ok;
    dp[1][0]=0;

    for(i=1;i<(1<<n);i++)
     for(j=0;j<n;j++)
      if (dp[i][j]!=ok)
       for(t=0;t<v[j].size();t++)
         { nod=v[j][t];
          if (!(i&(1<<v[j][t])))
           dp[i|(1<<nod)][nod]=min(dp[i|(1<<nod)][nod],dp[i][j]+c[j][nod]);
         }

   for(i=1;i<n;i++)
    {if (dp[(1<<n)-1][i]!=ok && c[i][0]!=ok)
     sol=min(sol,dp[(1<<n)-1][i]+c[i][0]);
    }

  g<<sol;
}
int main()
{ int i,x,y,cst;
    f>>n>>m;
    memset(dp,inf,sizeof(dp));
    memset(c,inf,sizeof(c));

    for(i=1;i<=m;i++)
    { f>>x>>y>>cst;
      c[x][y]=cst;
      v[x].push_back(y);
    }

    Solve();
    return 0;
}