#include <fstream>
#include <iostream>
#include <vector>
#include <cstring>
#define v first
#define c second
#define INF 0x7F7F7F7F
#define ULTSTARE ((1 << n)-1)

using namespace std;

vector<pair<int, int> > L[18];
int D[18][1<<18];
int M[18];

int n, m, i, x, y, cost, sol, stare, j, vecin, urmStare;

int main () {

    memset(D, 127, sizeof(D));
    memset(M, 127, sizeof(M));
    ifstream fin ("hamilton.in");
    ofstream fout("hamilton.out");

    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>cost;
        L[x].push_back(make_pair(y, cost));
        if (y == 0) {
            M[x] = cost;
        }
    }

    sol = INF;
//    cout<<D[1][1]<<"\n"<<INF;
    D[0][1] = 0;
    for (stare = 1; stare < (1<<n); stare+=2) {
        for (i=0;i<n;i++) {
            if (D[i][stare] != INF) {
                // trec din starea D[i][stare] in alta
                // caut vecinii
                for (j=0;j<L[i].size(); j++) {
                    vecin = L[i][j].v;
                    cost = L[i][j].c;
                    if ((stare & (1 << vecin)) == 0) {
                        urmStare = stare + (1 << vecin);
                        D[vecin][urmStare] = min(D[vecin][urmStare], D[i][stare] + cost);
                    }
                }
            }
        }
    }

    for (i=1;i<n;i++) {
        if (M[i] != INF && D[i][ULTSTARE] != INF) {
            sol = min(sol, D[i][ULTSTARE] + M[i]);
        }
    }
    if (sol != INF)
        fout<<sol;
    else
        fout<<"Nu exista solutie";
    return 0;
}