#include<fstream>
#define pinf 999999999
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int n,m,i,j,k,x,y,c,ans,ma[30][30],d[270000][30];
int main()
{
    fin>>n>>m;
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
        {
            ma[i][j]=pinf;
        }
    for(i=1;i<=(1<<n);i++)
        for(j=0;j<=n;j++)
            d[i][j]=pinf;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        ma[x][y]=c;
    }
    d[1][0]=0;
    for(i=1;i<=(1<<n);i+=2)
        for(j=1;j<n;j++)
        {
            if((1<<j) & i)
            {
                for(k=0;k<n;k++)
                {
                    if(d[i-(1<<j)][k]+ma[k][j]<d[i][j])
                        d[i][j]=d[i-(1<<j)][k]+ma[k][j];
                }
            }
        }
    ans=pinf;
    for(k=0;k<n;k++)
        if(d[(1<<n)-1][k]+ma[k][0]<ans)
            ans=d[(1<<n)-1][k]+ma[k][0];
    fout<<ans;



    fin.close();
    fout.close();
    return 0;
}