#include <bits/stdc++.h>

using namespace std;
int n,m,c[20][20],a[20][20],x,y,cost,d[262144][20];

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

const int INF=2e5;

int main()
{
    in>>n>>m;

       for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++) c[i][j]=INF;


     }



     int val=(1<<n);

    for(int i=0;i<val;i++)
      for(int j=0;j<n;j++) d[i][j]=INF;

    for(int i=1;i<=m;i++)
    {
        in>>x>>y>>cost;
        a[x][y]=1;
        c[x][y]=cost;



    }



    d[1][0]=0;

    for(int i=3;i<val;i+=2)
    {

       for(int j=0;j<n;j++)
       {
          if(i&(1<<j))
          {
             int ii=i^(1<<j);

             for(int jj=0;jj<n;jj++)
             {
                 if(ii & (1<<jj)) d[i][j]=min(d[i][j],d[ii][jj]+c[jj][j]);

             }

          }

       }

    }

    int mini=99999999;
    for(int i=0;i<n;i++) mini=min(mini,d[(1<<n)-1][i]+c[i][0]);

    out<<mini;



    return 0;
}