#include <iostream>
#include <fstream>

using namespace std;

fstream f;

int v[262144][18],power[18],muchii[18][18];
int i,j,k,l,m,n,sol;

int main()
{
    f.open("hamilton.in",ios_base::in);
    f>>n>>m;
    for(i=1,power[0]=1;i<=n;i++)power[i]=power[i-1]*2;
    for(i=1;i<=m;i++)
    {
        f>>j>>k>>l;
        muchii[j][k]=l;
    }
    f.close();
    v[1][0]=1;
    for(i=2;i<power[n];i++)for(j=0;j<n;j++)for(k=0;k<n;k++)if(muchii[k][j]!=0&&v[i^power[j]][k]!=0)
    {
        if(v[i][j]==0)v[i][j]=v[i^power[j]][k]+muchii[k][j];
        else v[i][j]=min(v[i^power[j]][k]+muchii[k][j],v[i][j]);
    }
    for(i=0;i<n;i++)if(v[power[n]-1][i]!=0&&muchii[i][0]!=0)
    {
        if(sol==0)sol=v[power[n]-1][i]+muchii[i][0];
        else sol=min(sol,v[power[n]-1][i]+muchii[i][0]);
    }
    f.open("hamilton.out",ios_base::out);
    f<<sol-1;
}