#include <fstream>
#include <vector>
#include <cstring>

#define MAXN 20
#define MAXC 262150
#define INF 0x3f3f3f3f

using namespace std;

int c[MAXC][MAXN], cost[MAXN][MAXN], n, m, sol;
vector<int> v[MAXN];

int calc(int conf, int nod)
{
    if(c[conf][nod] == -1)
    {
        c[conf][nod] = INF;
        for(int i = 0; i < v[nod].size(); i++)
            if(conf & (1 << v[nod][i]))
                c[conf][nod] = min(c[conf][nod], calc(conf ^ (1 << nod), v[nod][i]) + cost[v[nod][i]][nod]);
    }
    return c[conf][nod];
}

int main()
{
    ifstream in("hamilton.in"); in>>n>>m;
    int a, b; sol = INF;
    for(int i = 1; i <= m; i++)
    {
        in>>a>>b; in>>cost[a][b];
        v[b].push_back(a);

    }in.close();

    memset(c, -1, sizeof(c));
    c[1][0] = 0;
    for(int i = 0; i < v[0].size(); i++)
        sol = min(sol, calc((1<<n) - 1, v[0][i]) + cost[v[0][i]][0]);
    ofstream out("hamilton.out");
    if(sol == INF)
        out<<"Nu exista solutie";
    else
        out<<sol;
    out.close();
    return 0;
}