#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int v[18][18];
long long dp[(1<<18)][18];///dp[mask][i]=costul minim sa fi vazut mask cu final in i
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    int n,i,m,a,b,c,j,k;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        v[a][b]=c;
    }
    for(i=1;i<(1<<n);i++)
        for(j=0;j<n;j++)
            dp[i][j]=(long long)1e15;
    dp[1][0]=0;
    for(i=1;i<(1<<n);i+=2)
        for(j=1;j<n;j++)
            if((1<<j)&i)
                for(k=0;k<n;k++)
                    if(v[k][j]&&((1<<k)&i))
                        dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+v[k][j]);
    long long min1=(long long)1e15;
    for(j=1;j<n;j++)
        if(v[j][0]&&dp[(1<<n)-1][j]+v[j][0]<min1)
            min1=dp[(1<<n)-1][j]+v[j][0];
    if(min1==(long long)1e15)
        cout<<"Nu exista solutie";
    else
        cout<<min1;
    return 0;
}