#include<bits/stdc++.h>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
vector<int> v[20];
int cost[20][20],a[1<<18][20];
int solve(int nr,int j)
{
    if(a[nr][j]!=-1)
        return a[nr][j];
    a[nr][j]=1<<28;
    for(int i=0;i<v[j].size();i++)
        if((nr&(1<<v[j][i]))&&(v[j][i]||nr==(1<<j)+1))
            a[nr][j]=min(a[nr][j],solve(nr^(1<<j),v[j][i])+cost[v[j][i]][j]);
    return a[nr][j];
}
int main()
{
    int n,m,i,j,mn=1<<28,nr1,nr2;
    in>>n>>m;
    for(i=0;i<20;i++)
        for(j=0;j<20;j++)
            cost[i][j]=1<<28;
    memset(a,-1,sizeof(a));
    for(i=0;i<m;i++)
    {
        in>>nr1>>nr2>>cost[nr1][nr2];
        v[nr2].push_back(nr1);
    }
    a[1][0]=0;
    for(i=0;i<v[0].size();i++)
        mn=min(mn,solve((1<<n)-1,v[0][i])+cost[v[0][i]][0]);
    if(mn==1<<28)
        out<<"Nu exista solutie";
    else
        out<<mn;
    return 0;
}