#include <fstream>
#include <algorithm>

using namespace std;

#define pb push_back
#define mp make_pair
#define inf 20000005

int mat[20][20];
int din[20][262150]; //de vazut dim

int main()
{
    ifstream cin("hamilton.in");
    ofstream cout("hamilton.out");

    int n,m,i,j,k,a,b,c;
    cin>>n>>m;

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            mat[i][j]=inf;

    for(i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        mat[a][b]=c;
    }


    din[0][1]=0;

    for(i=2;i<(1<<n);i++)
    {
        for(j=0;j<n;j++)
            din[j][i]=inf;

        if(i&(i-1))
            for(j=0;j<n;j++)
            {
                if(i&(1<<j))
                    for(k=0;k<n;k++)
                        if(i&(i<<k))
                            din[j][i]=min(din[j][i],din[k][i-(1<<j)]+mat[k][j]);
                //cout<<"din["<<j<<"]["<<i<<"]="<<din[j][i]<<endl;
            }
    }

    int minim=inf;
    for(j=1;j<n;j++)
    {
        //cout<<"din["<<j<<"]["<<(1<<n)-1<<"]="<<din[j][(1<<n)-1]<<" + "<<mat[j][0]<<endl;
        if((mat[j][0]+din[j][(1<<n)-1])<minim)
            minim=mat[j][0]+din[j][(1<<n)-1];
    }

    if(minim==inf)
        cout<<"Nu exista solutie\n";
    else
        cout<<minim<<'\n';

    cin.close();
    cout.close();
    return 0;
}