#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#define inf 100000000

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,i,j,k,m,x,y,n2,c2,vecin,cost[20][20],c[550000][20],sol;
vector<int> a[20];

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c2;
        a[y].push_back(x);
        cost[y][x]=c2;
    }
    for(i=0;i< 1<<n;i++)
        for(j=0;j<n;j++) c[i][j]=inf;
    c[1][0]=0;
    for(i=1;i< 1<<n;i++)
    for(j=0;j<n;j++)
    {
        if(i&(1<<j))
        {
            for(k=0;k<a[j].size();k++)
            {
                vecin=a[j][k];
                if(i&(1<<vecin))
                {
                    c[i][j]=min(c[i][j],c[i^(1<<j)][vecin]+cost[j][vecin]);
                }
            }
        }
    }
    sol=inf;
    for(i=0;i<a[0].size();i++) sol=min(sol,c[1<<n-1][a[0][i]]+cost[0][a[0][i]]);
    if(sol==inf) g<<"Nu exista solutie"<<'\n';
    else g<<sol<<'\n';
    return 0;
}