#include <bits/stdc++.h>
#define NMAX 20
#define MOD 1000000007
using namespace std;
typedef long long ll;
int v[NMAX][NMAX],dp[NMAX][270000];
int main()
{
    int n,m,i,k,x,y,c,j,val,ans;
    memset(v,63,sizeof(v));
    memset(dp,63,sizeof(dp));
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    cin>>n>>m;
    if(n==1)
    {
        cout<<"Nu exista solutie"<<'\n';
        return 0;
    }
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        v[x+1][y+1]=c;
    }
    dp[1][1]=0;
    for(k=1;k<(1<<n);k++)
    {
        for(i=1;i<=n;i++)
        {
            if(((1<<(i-1))&k)==0) continue;
            for(j=2;j<=n;j++)
            {
                val=(1<<(j-1));
                if((val&k)!=0) continue;
                dp[j][k|val]=min(dp[j][k|val],dp[i][k]+v[i][j]);
            }
        }
    }
    val=(1<<n)-1;
    ans=dp[1][val];
    for(i=2;i<=n;i++)
        ans=min(ans,dp[i][val]+v[i][1]);
    if(ans==dp[1][val])
    {
        cout<<"Nu exista solutie"<<'\n';
        return 0;
    }
    cout<<ans<<'\n';
    return 0;
}