#include <bits/stdc++.h>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
typedef long long ll;
int n,m;
int dp[20][(1<<18)];
int x,y,c;
int adi[20][20];
vector <pair<int,int>> v[20];

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        adi[i][j]=1e9;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[y].push_back({x,c});
        adi[x][y]=c;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<(1<<n);j++)
        dp[i][j]=1e9;
    dp[0][1]=0;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
        if((i&(1<<j)))//e in masca
    {
        for(int q=0;q<v[j].size();q++)
        if(((1<<v[j][q].first)&i))
            dp[j][i]=min(dp[j][i],dp[v[j][q].first][i^(1<<j)]+v[j][q].second);
    }
    ll sol=1e9;
    for(int i=0;i<v[0].size();i++)
    {
        sol=min(sol,dp[v[0][i].first][(1<<n)-1]+v[0][i].second);
    }
    if(sol==1e9)
        fout<<"Nu exista solutie";
    else
        fout<<sol;
    return 0;
}