#include <fstream>
#include <vector>
#define DIM 18
#define INF 2000000000
using namespace std;

ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
int n,m,i,j,s,vecin,x,y,cost,sol,d[(1<<DIM)][DIM];
vector < pair<int,int> > L[DIM];

void initializare (){
    for (int i=0;i<(1<<n);i++)
        for (int j=0;j<n;j++)
            d[i][j] = INF;
    d[1][0] = 0;
}
int main (){

    fin>>n>>m;
    for (i=1;i<=m;i++){
        fin>>x>>y>>cost;
        L[y].push_back (make_pair(x,cost));
    }
    initializare ();
/// d[submultimea de noduri vizitate][cine e ultimul]
    for (s=3;s<(1<<n);s+=2)
        for (i=0;i<n;i++)
            if (s & (1<<i))
                for (j=0;j<L[i].size();j++){
                    vecin = L[i][j].first;
                    if (!(s & (1<<vecin)))
                        continue;
                    x = d[s-(1<<i)][vecin] + L[i][j].second;
                    if (x < d[s][i])
                        d[s][i] = x;
                }


    sol = INF;
    for (i=0;i<L[0].size();i++){
        vecin = L[0][i].first;
        sol = min (d[(1<<n)-1][vecin] + L[0][i].second,sol);
    }
    if (sol == INF)
        fout<<"Nu exista solutie";
    else
        fout<<sol;

    return 0;
}