#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define N 20
#define pb push_back
#define ST 1<<20
#define inf 1<<30
int l,d[N][ST],i,j,n,m,k,c,v[N],x;
///d[i][stare] costul ciclului care se termina cu i si contine varfurile marcate cu 1 in reprezentarea binara a lui stare
struct nod
{
    int x,c;
}e;
vector<nod>a[N];
int main()
{
    ifstream f("hamilton.in");
    f>>n>>m;
    for(l=0;l<m;++l)
    {
        f>>e.x>>i>>e.c;
        a[i].pb(e);///retin din ce noduri pot ajunge in i
        ++v[i];
    }
    for(i=0;i<n;++i)
        for(j=0;j<(1<<n);++j)
            d[i][j]=inf;
    d[0][1]=0; ///setez startul in nodul 0;
    for(j=0;j<(1<<n);++j)
    {
        for(i=0;i<n;++i)
            if( j&(1<<i) )///verificare daca i are bitul 1 in reprezentarea lui j
                for(l=0;l<v[i];++l)
                {
                    x=a[i][l].x;
                    c=a[i][l].c;
                    if( j&(1<<x) )///verific daca vecinul lui i apare in j
                        d[i][j]=min( d[x][j ^ (1<<i) ] + c , d[i][j] );
                }
    }
    int sol=inf;
    for(l=0;l<v[0];++l)
    {
        x=a[0][l].x;
        c=a[0][l].c;
        sol=min(sol,d[x][ (1<<n) -1 ] + c );
        //cout<<x<<" "<<c<<" "<<sol<<'\n';
    }
    ofstream g("hamilton.out");
    if(sol==inf)
        g<<"Nu exista solutie";
    else g<<sol;
    return 0;
}