#include <fstream>
#include <vector>
#define INF 100000000
using namespace std;
int C[262150][18];
int main()
{
    int n, m, graph[18][18];
    vector <int> A[18];
    ifstream in("hamilton.in");
    in >> n >> m;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            graph[i][j] = INF;
    for(int a, b; m; --m)
    {
        in >> a >> b;
        in >> graph[a][b];
        A[b].push_back(a);
    }
    in.close();
    for (int i = 0; i < 1 << n; ++i)
		for (int j = 0; j < n; ++j)
            C[i][j] = INF;
    C[1][0] = 0;
    for(int i = 0; i < (1<<n); ++i)
        for(int j = 0; j < n; ++j)
            if(i & (1<<j))
                for(int k = 0; k < A[j].size(); ++k)
                    if (i & (1<<A[j][k]))
                        C[i][j] = min(C[i][j], C[i^(1<<j)][A[j][k]] + graph[A[j][k]][j]);
    int res = INF;
    for(int i = 0; i < A[0].size(); ++i)
        res = min(res, C[(1<<n)-1][A[0][i]]+graph[A[0][i]][0]);
    ofstream out("hamilton.out");
    if(res==INF)
        out << "Nu exista solutie";
    else
        out << res;
    out.close();
    return 0;
}