#include <fstream>
#include <vector>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
vector<int> a[19];
int n, m, i,j, x,y,c,b[19][19],d[262165][19],pr,k,minim;
int main()
{
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        a[y].push_back(x);
        b[x][y]=c;
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
            d[i][j]=100000000;
    d[1][0]=0;
    for(i=1;i<(1<<n);i=i+2)
        for(j=0 ;j<n;j++)
            if((i&(1<<j))!=0)
            {
                for(k=0;k<a[j].size();k++)
                {
                    pr=a[j][k];
                    if(d[i^(1<<j)][pr]+b[pr][j]<d[i][j])
                    {
                        d[i][j]=d[i^(1<<j)][pr]+b[pr][j];
                    }
                }
            }



    x=0; minim=100000000; y=1;
    for(i=0;i<n;i++)
    {
        x=x+y;
        y=y*2;
    }
    for(i=0;i<a[0].size();i++)
    {
        y=a[0][i];
        if(d[x][y]+b[y][0]<minim)
            minim=d[x][y]+b[y][0];
    }
    out<<minim;
    /*  for(i=1;i<(1<<n);i++)
    {
        for(j=0;j<n;j++)
        {
            out<<d[i][j]<<" ";
        }
        out<<"\n";

    }*/
     return 0;
}