#include <fstream>
#include <vector>
#define DIM 18
#define INF 100000000

using namespace std;

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

vector< pair<int, int> > L[DIM];
vector< pair<int, int> > K[DIM];
int D[1<<DIM][DIM];

int n, m, c, x, y, i, minim, j, stare, nod;


int main(){
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        //L[x].push_back( make_pair(y,c) );
        K[y].push_back( make_pair(x,c) );
    }

    for (i=0;i<(1<<n);i++)
        for (j=0;j<n;j++)
            D[i][j] = INF;

    D[1][0] = 0;

    for (stare=3; stare<(1<<n); stare+=2)
        for (nod = 0; nod<n; nod++)
            if (stare & (1<<nod)) {

                for (int i=0;i<K[nod].size();i++) {
                    int x = K[nod][i].first;
                    if (!(stare & (1<<x)))
                        continue;
//                    rec(stare-(1<<nod), x);
                    y = D[stare-(1<<nod)][x] + K[nod][i].second;
                    if (D[stare][nod] > y)
                        D[stare][nod] = y;
                }
            }

    minim = INF;

    for (i=0;i<K[0].size();i++) {
        //rec((1<<n)-1, K[0][i].first);
        if (minim > D[(1<<n)-1][K[0][i].first] + K[0][i].second)
            minim = D[(1<<n)-1][K[0][i].first] + K[0][i].second;
    }
    if (minim != INF)
        fout<<minim;
    else
        fout<<"Nu exista solutie";
    return 0;
}