#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
#define MAX 19
#define INF 1<<30
int c[1<<MAX][MAX], cost[MAX][MAX];

vector <int> G[MAX];

int main()
{
    int n, m, i, j, k, x, y, z, V, sol;
    fin>>n>>m;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            cost[i][j]=INF;
        }
    }
    while(m--)
    {
        fin>>x>>y>>z;
        G[y].push_back(x);
        cost[x][y]=z;
    }
    for(i=1;i<(1<<n);i++)
    {
        for(j=0;j<n;j++)
        {

            c[i][j]=INF;
            c[1][0]=0;
            if(!(i & (1 << j)))
                continue;
            for(k=0;k<G[j].size();k++)
            {
                V=G[j][k];
                if(!(i & (1 << V)))
                    continue;
                c[i][j]=min(c[i][j], c[i ^ (1 << j)][V] + cost[V][j]);
            }

        }
    }
    sol=INF;
    for(i=0;i<G[0].size();i++)
    {
        V=G[0][i];
        sol=min(sol, c[(1<<n)-1][V]+cost[V][0]);
    }
    if(sol==INF)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
}