#include <fstream>
#include <vector>
#include <cstring>
#define nmax 18
#define inf 100000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n, m, x, y, c, w[nmax][nmax], C[(1<<nmax)][nmax], res=inf;
vector<int> G[nmax];

int solve(int seen, int to) {
    if(C[seen][to]==-1) {
        C[seen][to]=inf;
        for(auto i:G[to])
            if(seen&(1<<i)) {
                if(i==0 && seen!=(1<<to)+1)
                    continue;
                C[seen][to]=min(C[seen][to], solve(seen^(1<<to), i)+w[i][to]);
            }
    }
    return C[seen][to];
}

int main() {
    f>>n>>m;

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            w[i][j]=inf;

    for(int i=1;i<=m;i++) {
        f>>x>>y>>c;
        G[y].push_back(x);
        w[x][y]=c;
    }

    memset(C, -1, sizeof(C));
    C[1][0]=0;

    for(auto i:G[0])
        res=min(res, solve((1<<n)-1, i)+w[i][0]);

    if(res==inf)
        g<<"Nu exista solutie";
    else
        g<<res;

    f.close();
    g.close();
    return 0;
}