#include <iostream>
#include <fstream>
#include <vector>
#define Nmax 19
#define Mmax (1<<18)
#define oo 100000000
using namespace std;
 ifstream fin("hamilton.in");
 ofstream fout("hamilton.out");
 vector <int> A[Nmax];
 int C[Nmax][Nmax],DP[Mmax][Nmax],n,m;
 void read()
 {

     fin>>n>>m;
     int i,j;
     for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            C[i][j]=oo;

     for(i=1;i<=m;i++)
     {
         int x,y,c;
         fin>>x>>y>>c;
         C[x][y]=c;
         A[y].push_back(x);
     }
 }

 ///DP[i][j]=costul minim din configuratia i ce se termina in j

  void solve()
 {
     int i,j;
     for(i=0;i<1<<n;i++)
        for(j=0;j<n;j++)
            DP[i][j]=oo;

     DP[1][0]=0;
     for(i=0;i<1<<n;i++)
     for(j=0;j<n;j++)
        if(i&(1<<j))                                                                 ///daca e in config
        for(unsigned int k=0;k<A[j].size();k++)
            if(i&(1<<A[j][k]))                                                          ///daca vecinul e in configuarie
            DP[i][j]=min(DP[i][j], DP[i^(1<<j)][A[j][k]] + C[A[j][k]][j]);          ///scot i din config


     int sol=oo;
     for(unsigned int i=0;i<A[0].size();i++)
        sol=min(sol,DP[(1<<n)-1][A[0][i]] + C[A[0][i]][0]);                                      ///configuratii cu toate elem

     if(sol==oo) fout<<"Nu exista solutie";
     else
        fout<<sol;

 }
int main()
{
   read();
   solve();
    return 0;
}