#include <bits/stdc++.h>

using namespace std;

const int INF = 2000000005;
int n, m, c[30][30], pd[(1<<18)+1][30], ans = INF;
vector<int> v[30];

int rec(int conf, int last)
{
    if(pd[conf][last] != -1)
        return pd[conf][last];
    pd[conf][last] = INF;
    for (vector<int>::iterator it = v[last].begin(); it != v[last].end(); ++it)
        if(conf & (1 << (*it)) && !(*it == 0 && conf != (1<<last)+1))
            pd[conf][last] = min(pd[conf][last], rec(conf ^ (1<<last), *it) + c[*it][last]);
    return pd[conf][last];
}

int main()
{
    memset(c, -1, sizeof(c));
    memset(pd, -1, sizeof(pd));
    ifstream fin ("hamilton.in");
    ofstream fout ("hamilton.out");
    fin >> n >> m;
    while(m--){
        int x, y, z;
        fin >> x >> y >> z;
        c[x][y] = z;
        v[y].push_back(x);
    }
    pd[1][0] = 0;
    for (vector<int>::iterator it = v[0].begin(); it != v[0].end(); ++it)
        ans = min(ans, rec((1<<n)-1, *it)+c[*it][0]);
    if(ans == INF)
        fout << "Nu exista solutie\n";
    else fout << ans << "\n";
    fin.close();
    fout.close();
    return 0;
}