#include <bits/stdc++.h>
#define Dmax 20
#define inf 0x3F3F3F3F
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,sol,Cost[Dmax][Dmax],C[262150][Dmax];
vector<int>G[Dmax];
int main()
{
    f>>n>>m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            Cost[i][j] = inf;
    for(int i = 1; i <= m; i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        G[y].push_back(x);
        Cost[x][y] =z;
    }
    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 mask = 3; mask < 1<<n; mask+=2)
            for(int i = 0; i < n; i++)
                if(mask & (1<<i))
                    for(vector<int>::iterator it = G[i].begin(); it < G[i].end(); it++)
                        C[mask][i] = min(C[mask][i], C[mask ^ (1<<i)][*it] + Cost[*it][i]);
        sol = inf;
        for(vector<int>::iterator it = G[0].begin(); it < G[0].end(); it++)
            sol = min(sol,C[(1<<n)-1][*it] + Cost[*it][0]);

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


    return 0;
}