#include <bits/stdc++.h>
#define inf INT_MAX
using namespace std;

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

vector<vector<int>> v, m;
vector<int> pw2;
int n, M, x, y, z;
void precalc();
void read();
void make_m();
void rez();

int main(){
    precalc();
    read();
    make_m();
    rez();
    return 0;
}
void precalc(){
    pw2 = vector<int>(20);
    pw2[0] = 1;
    for (int i = 1; i < 20; i++)
        pw2[i] = pw2[i-1] * 2;
}
void read(){
    fin >> n >> M;
    v = vector<vector<int>>(n, vector<int>(n));
    m = vector<vector<int>>(pw2[n-1], vector<int>(n));
    for (int i = 0; i < M; i++){
        fin >> x >> y >> z;
        v[x][y] = z;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (v[i][j] == 0)
                v[i][j] = INT_MAX / 2;
}
void make_m(){
    for (int i = 1; i < n; i++){
        m[pw2[i-1]][i] = v[0][i];
    }
    for (int i = 1; i < pw2[n-1]; i++){
        for (int nod = 1; nod < n; nod++){
            if (m[i][nod] != 0)
                continue;
            m[i][nod] = INT_MAX / 2;
            if (i / pw2[nod-1] % 2 == 1){
                for (int nod2 = 1; nod2 < n; nod2++){
                    m[i][nod] = min(m[i][nod], m[i-pw2[nod-1]][nod2] + v[nod2][nod]);
                }
            }
        }
    }
}
void rez(){
    int rez = INT_MAX / 2;
    for (int nod = 1; nod < n; nod++){
        rez = min(rez, m[pw2[n-1]-1][nod] + v[nod][0]);
    }
    if (rez == INT_MAX / 2)
        fout << "Nu exista solutie";
    else
        fout << rez;
}