#include <bits/stdc++.h>

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

int n,m,v[20][20],rez[1<<20][20];
int INF = 1<<30;

int main()
{
    in>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        int x,y,pret;
        in>>x>>y>>pret;
        v[x][y] = pret;
    }
    for(int i = 0;i < 1<<n;i++)
        for(int j = 0;j < n;j++)
            rez[i][j] = INF;
    rez[1][0] = 0;
    for(int mask = 1;mask < 1<<n;mask++)
    {
        for(int last = 0;last < n;last++)
        {
            if(mask & (1<<last) != 0)
            {
                for(int i = 0;i < n;i++)
                {
                    if((mask & (1<<i)) == 0 && v[last][i])
                    {
                        int nr = mask | (1<<i);
                        rez[nr][i] = min(rez[nr][i], rez[mask][last] + v[last][i]);
                    }
                }
            }
        }
    }
    int mx = INF;
    for(int i = 1;i < n;i++)
    {
        if(v[i][0] && rez[(1<<n)  -1][i])
            mx = min(mx, rez[(1<<n)  -1][i] + v[i][0]);
    }
    if(mx == INF)
        out<<"Nu exista solutie";
    else
        out<<mx;

    return 0;
}