#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");

const int MAXN=20;
const int MAXX=262150;
const int INF=100000000;
int n,m,Sol,q;
int Cost[MAXN][MAXN],C[MAXX][MAXN];
vector <int> A[MAXN];  ///F.imp, dar am uitat dc

int main()
{
    fin>>n>>m;
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)Cost[i][j]=INF;
    for(int i=1;i<=m;++i){
        int x,y;
        fin>>x>>y;
        A[y].push_back(x); ///adaug x in lista de vecini a lui y;
        fin>>Cost[x][y]; ///citesc costul arcului
    }

    ///costul de la orice submultime la fiecare varf = infinit
    for(int i=0;i<32;++i)
        for(int j=0;j<5;++j)
         {C[i][j]=INF;///cout<<++q<<": "<<i<<' '<<j<<'\n';
         }

    ///costul minim de la 0 la 0 este 0(primul bit este bitul 0)
    C[1][0]=0;


    for(int i=0;i<(1<<n);++i)
        for(int j=0;j<n;++j)
         if(i &(1<<j)) ///daca j face parte din multimea i
          for(int k=0;k<A[j].size();++k) ///parcurg lista vecinilor lui k
           if(i & (1<<A[j][k])) ///pentru fiecare nod din multime
            C[i][j]=min(C[i][j], C[i^(1<<j)][A[j][k]]+Cost[A[j][k]][j]);

    ///pentru ca nu conteaza de unde plecam, vom considera lanturile care
    ///pornesc din 0 si se termina in 0, trecand prin toate celelalte noduri
    ///se obtine, de fapt, un ciclu hamiltonian

    Sol=INF;
    for(int i=0;i<A[0].size();++i)
        Sol=min(Sol, C[(1<<n)-1][A[0][i]]+Cost[A[0][i]][0]);
    if(Sol==INF)fout<<"Nu exista solutie";
    else fout<<Sol;


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