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

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");

const int Xmax = 262150;
const int Nmax = 20;
const int oo = 1000000000;
int n, m, cost[Nmax][Nmax], C[Xmax][Nmax], sol;
vector <int> G[Nmax];

int Calc(int conf, int last)
{
    if(C[conf][last] == -1)
    {
        C[conf][last] = oo;
        for(int i = 0; i < (int)G[last].size(); i++)
            if(conf & (1<<G[last][i]))
                C[conf][last] = min(C[conf][last], Calc(conf^(1<<last), G[last][i]) + cost[G[last][i]][last]);
    }
    return C[conf][last];
}

int main()
{
    sol = oo;
    f>>n>>m;
    int x,y;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++) cost[i][j] = oo;
    for(int i = 1; i <= m; i++)
    {
        f>>x>>y;
        G[y].push_back(x);
        f>>cost[x][y];
    }
    memset(C, -1, sizeof(C));
    C[1][0] = 0;
    for(int i = 0; i < (int)G[0].size(); i++)
        sol = min(sol, Calc((1<<n) - 1, G[0][i]) + cost[G[0][i]][0]);
    if(sol == oo) g<<"Nu exista solutie";
    else g<<sol<<'\n';
    return 0;
}