#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
const int N=19;
const int N2=(1<<N);
const int INF=1e9;
int cost[N][N];
int dp[N2][N];
vector<int> a[N];
int main()
{
    int n,m,i,x,y,c,sol=INF,j,k;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        a[y].push_back(x);
        cost[x][y]=c;
    }
    for(i=1;i<(1<<n);i++)
    for(j=0;j<n;j++)
        dp[i][j]=INF;
    dp[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++)
                if(i&(1<<a[j][k]))
                    dp[i][j]=min(dp[i][j],dp[i-(1<<j)][a[j][k]]+cost[a[j][k]][j]);
        }
    }
    for(i=1;i<n;i++)
        if(cost[i][0])
            sol=min(sol,dp[(1<<n)-1][i]+cost[i][0]);
    if(sol==INF)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}