#include <bits/stdc++.h>
#define MAXN 20
#define MAXX 262150
#define oo 1000000000
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,sol;
vector<int> A[MAXN];
int C[MAXX][MAXN];
int Cost[MAXN][MAXN];

int calc(int conf,int last)
{
    if(C[conf][last] == -1)
    {
        C[conf][last] = oo;
        for(int i = 0;i < A[last].size();++i)
            if(conf & (1 << A[last][i]))
            {
                if(A[last][i] == 0 && conf != (1 << (last)) + 1) continue;

                C[conf][last] = min(C[conf][last], calc(conf ^ (1 << last),A[last][i]) + Cost[A[last][i]][last]);
            }
    }
    return C[conf][last];
}

void Read()
{
    sol = oo;
    f>>n>>m;
    for(int i = 0;i < n;++i)
        for(int j = 0;j < n;++j)
            Cost[i][j] = oo;
    int x,y;
    for(int i = 1;i <=m;++i)
    {
        f>>x>>y;
        A[y].push_back(x);
        f>>Cost[x][y];
    }
    memset(C,-1,sizeof(C));
    C[1][0] = 0;

    for(int i = 0;i < A[0].size();++i)
        sol = min(sol, calc((1<<n) - 1,A[0][i]) + Cost[A[0][i]][0]);
    if(sol == oo)
        g<<"Nu exista solutie"<<'\n';
    else g<<sol<<'\n';
}
int main()
{
    Read();
    return 0;
}