#include <fstream>
#define INF 1000000000

using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

int n,Cost[20][20],dp[(1<<18)][20];

int main()
{
    int m,x,y,c,sol=INF,i,j,k;
    cin>>n>>m;
    if(n==1) {
        cout<<0; return 0;
    }
    while(m--) {
        cin>>x>>y>>c;
        Cost[x][y]=c;
    }
    for(i=0;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) {
            for(k=0;k<n;++k)
                if(!((1<<k)&i) && Cost[j][k]) dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+Cost[j][k]);
        }
    for(i=1;i<n;++i)
        if(Cost[i][0])
            sol=min(sol,dp[(1<<n)-1][i]+Cost[i][0]);

    if(sol==INF) cout<<"Nu exista solutie";
    else cout<<sol;

    return 0;
}