#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
int v[18][18];
long long dp[(1<<18)][17];///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;
    for(int care=1,j=3;j<(1<<n);j=j*2-1,care++)
        if(v[0][care])
            dp[j][care-1]=v[0][care];
    for(i=1;i<(1<<n);i+=2)
        if(__builtin_popcount(i)>=3)
            for(j=1;j<n;j++)
                if((1<<j)&i)
                    for(k=1;k<n;k++)
                        if(v[k][j]&&((1<<k)&i))
                            dp[i][j-1]=min(dp[i][j-1],dp[i^(1<<j)][k-1]+v[k][j]);
    long long min1=(long long)1e15;
    for(j=1;j<n;j++)
        if(v[j][0]&&dp[(1<<n)-1][j-1]+v[j][0]<min1)
            min1=dp[(1<<n)-1][j-1]+v[j][0];
    if(min1==(long long)1e15)
        cout<<"Nu exista solutie";
    else
        cout<<min1;
    return 0;
}