//Balcau Ionut - grupa 134

using namespace std;

#include <fstream>
#include <vector>
#include <algorithm>

ofstream fout("hamilton.out");

int n, m, s;
vector< vector<int> > c, cmin;
vector<int> g[20];

void citire(){
ifstream fin("hamilton.in");
    
    int x, y;
    fin >> n >> m;
    c.resize(n, vector<int>(n, 1<<30));
    cmin.resize(1<<n, vector<int>(n, 1<<30));
    while(m--) {
        fin>>x>>y;
        g[y].push_back(x);
        fin >> c[x][y];
    }
}


int solve() {
    vector<int>::iterator it;
    int i, j;
    cmin[1][0] = 0;
    for(i=0; i<(1<<n); ++i)
        for(j=0; j<n; ++j)
            if(i & (1<<j))
                for(it=g[j].begin(); it!=g[j].end(); ++it)
                    if(i & (1<<*it))
                        cmin[i][j] = min(cmin[i][j], cmin[i^(1<<j)][*it] + c[*it][j]);
    for(it=g[0].begin(); it!=g[0].end(); ++it)
        s = min(s, cmin[(1<<n)-1][*it] + c[*it][0]);
}


int main() {
    citire();
    s=1<<30;
    s=solve();

    
    if(s == 1<<30) fout << "Nu exista solutie";
    else fout << s;
    fout.close();
    return 0;
}