#include <bits/stdc++.h>
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,m,i,j,a,b,c,mask,cmin=INT_MAX;
int cost[20][20];
int dp[20][1<<18+1];
int main()
{
    f>>n>>m;
    for (i=0;i<n;i++)
            for (j=0;j<n;j++)cost[i][j]=1e9;
    for (i=0;i<m;i++){f>>a>>b>>c;cost[a][b]=c;}
    int limit=(1<<n);
    for (mask=0;mask<limit;mask++){
        for (i=0;i<n;i++){
            dp[i][mask]=1e9;
        }
    }
    dp[0][1]=0;
    for (mask=3;mask<limit;mask++){
        for (i=0;i<n;i++)
            if (mask&(1<<i))
                for (j=0;j<n;j++)
                    if (mask&(1<<j)){
    dp[i][mask]=min(dp[i][mask],dp[j][mask-(1<<i)]+cost[j][i]);
                    }
    }
    for (i=0;i<n;i++){
        if (cmin>dp[i][(1<<n)-1]+cost[i][0]){
                cmin=dp[i][(1<<n)-1]+cost[i][0];
    //cout<<cmin<<'\n';
        }
    }
    if (cmin!=1e9)
    g<<cmin<<'\n';
    else g<<"Nu exista solutie";
    return 0;
}