#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;
    }

    for(i=1;i<n;i++)
        din[i][0]=mat[0][i];

    for(i=2;i<(1<<n);i++)
        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]);
            }
            else
                din[j][i]=inf;

    if(din[0][(1<<n)-1]==inf)
        cout<<"Nu exista solutie\n";
    else
        cout<<din[0][(1<<n)-1]<<'\n';

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