#include<fstream>
#include<vector>
#define M 1<<30
#define maxN 19
#define maxM 342
#define maxX 1<<20
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m,cost[maxN][maxN];
int c[maxX][maxN];
vector<int> Graph[maxN];
void citire()
{
    int i,j,a,b,c;
    f>>n>>m;
     for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cost[i][j]=M;

    for(int i=1;i<=m;i++)
    {
        f>>a>>b>>c;
        Graph[b].push_back(a);
        cost[a][b]=c;
    }

}
void solve()
{
    int i,j,SOL;
    for(i=0;i < 1<<n ;++i)
        for(j=0;j<n;++j)
            c[i][j]=M;
    c[1][0]=0; // de la 0 la 0 avem costul minim 0
    for ( i = 0 ; i < 1<<n ; ++i) // pentru toate configuratiile posibile 10001000100010 .. 001
         for ( j = 0 ; j < n ; ++j)
            if ( i & 1<<j ) // pentru fiecare nod ce se gaseste in configuratie
            {
                for ( auto e : Graph[j] ) // cautam nodurile ce "intra" in el
                {
                    if ( i & 1<<e ) // a.i sa fie si ele in configuratie
                        c[i][j] = min ( c[i][j] , c[i ^ (1<<j) ][e] + cost[e][j]  ) ; // actualizam minimul
                }
            }
    SOL = M;
    for( auto e : Graph[0] )
         SOL = min ( SOL , c[ (1<<n) - 1 ][e] + cost[e][0]  ) ;
    if ( SOL == M )
        g<<"Nu exista solutie";
    else g<<SOL<<'\n';
}
int main()
{
    citire();
    solve();
    return 0;
}